Problem E. Explorer kit

Author:И. Блинов   Time limit:2 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

Risorius is playing his favorite game, Doka 2, where a new event, "Fallen Crown," has been added. The event is represented as a sequence of n consecutive transitions. When at checkpoint i, Risorius can only transition to checkpoint i + 1. To move from checkpoint i to checkpoint i + 1, three tokens ti1, ti2, ti3 must be collected. After transitioning from one checkpoint to the next, all accumulated tokens are lost.

The game includes h heroes, and for defeating the j-th hero, tokens tj1, tj2, tj3 are awarded. The probability of Risorius winning against the k-th hero is pk. Additionally, if the player loses against a particular hero 10 times consecutively while staying on the same checkpoint, they are awarded all three tokens regardless of the outcome.

The event starts at checkpoint 0 and ends upon reaching checkpoint n. Find the expected number of matches Risorius must play to complete the event, assuming optimal strategy.

Input format

The first line contains a single integer n. The next n lines each contain three integers ti1, ti2, ti3 (for each checkpoint). The following line contains a single integer h. The next h lines each contain four integers tj1, tj2, tj3, and pj (for each hero, where pj represents the win probability). It is guaranteed that a solution always exists.

Output format

Output a single floating-point number with two decimal places, representing the expected value of the number of matches required.

Constraints

1 ≤ n, h ≤ 100000 1 ≤ ti1, ti2, ti3, tj1, tj2, tj3 ≤ 109 0 ≤ pj ≤ 100

Sample tests

No. Standard input Standard output
1
3
1 2 3
1 1 1
3 4 5
5
1 2 2 50
1 3 4 25
5 1 1 25
5 5 5 100
6 7 8 100
16.32
2
1
1 1 1
1
1 2 2 50
5.99

0.080s 0.011s 13