Задача E. Explorer kit ≡

Условие

Рисориус играет в свою любимую игру Дока 2, внутри игры добавили событие Павшая корона. Событие представимо в виде цепочки из n последовательных переходов, находясь на чекпоинте i можно перейти только на чекпоинт i + 1. Для прохода от чекпоинта i на чекпоинт i + 1 надо собрать три жетона t_i1, t_i2, t_i3. После перехода от одного чекпоинта к другому все накопленные жетоны сгорают.

В игре всего h героев, за победу на j-м герое дают жетоны t_j1, t_j2, t_j3. Вероятность того, что Рисориус победит на k-м герое p_k. Кроме того если игрок проигрывает на одном герое 10 раз подряд, находясь на одном чекпоинте, он всё равно получает все три жетона.

Прохождение события начинается на чекпоинте 0, а заканчивает при достижении чекпоинта n. Найдите математическое ожидание количества сыгранных Рисориус матчей необходимых для прохождения события, если она будет действовать оптимально.

Формат входных данных

Первая строка содержит одно целое число n. Далее следует n троек чисел t_i1, t_i2, t_i3. Следующая строка содержит одно целое число h. Далее следует h четвёрок целых чисел t_j1, t_j2, t_j3 и p_j. Гарантируется, что решение всегда существует.

Формат выходных данных

Выведите одно вещественное число с точностью до двух знаков после запятой  — математическое ожидание количества необходимых игр.

Ограничения

1 ≤ n, h ≤ 100000 1 ≤ t_i1, t_i2, t_i3, t_j1, t_j2, t_j3 ≤ 10⁹ 0 ≤ p_j ≤ 100

Примеры тестов

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