Problem E. Explorer kit ≡

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 t_i1, t_i2, t_i3 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 t_j1, t_j2, t_j3 are awarded. The probability of Risorius winning against the k-th hero is p_k. 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 t_i1, t_i2, t_i3 (for each checkpoint). The following line contains a single integer h. The next h lines each contain four integers t_j1, t_j2, t_j3, and p_j (for each hero, where p_j 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 ≤ t_i1, t_i2, t_i3, t_j1, t_j2, t_j3 ≤ 10⁹ 0 ≤ p_j ≤ 100

Sample tests

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

1
1 1 1
1
1 2 2 50

5.99