Вы хотите поставить рекорд в вашей любимой компьютерной игре. Игра состоит из N уровней, чтобы выиграть, вы должны пройти их друг за другом. Вы обычно проходите каждый уровень так быстро, как можете. но иногда вы проходите его медленнее. А именно, вы проходите i-й уровень либо за Fi секунд, либо за Si секунд, при этом Fi < Si, при этом с вероятностью Pi процентов вы пройдете его за Fi секунд. После прохождения уровня вы можете либо продолжить игру, перейдя на следующий уровень, либо сбросить прогресс и начать с первого уровня заново. Оба решения и действия вы совершаете мгновенно.
Ваша цель — пройти все уровни один за другим суммарно не более чем за R секунд. Вы хотите минимизировать ожидаемое время игры до момента, когда вы достигнете эту цель. Если вы будете продолжать и сбрасывать прогресс оптимально, чему равно математическое ожидаемое время игры?
Выходные данные
Выведите математическое ожидание времени игры. Ваш ответ будет считаться правильным, если его абсолютная или относительная точность не превосходит 10 - 9.
Формально, если ваш ответ равен a, а ответ жюри равен b, то ваш ответ будет считаться правильным, если 
.
Примечание
В первом примере вам никогда не надо начинать сначала. С вероятностью 81% вы закончите игру за 2 секунды, и с вероятностью 19% — за 8 секунд. И то и другое вас устроит. Ожидаемое время игры равно 0.81·2 + 0.19·8 = 3.14.
Во втором примере вы должны сбрасывать после первого уровня, если прошли его медленно. В среднем у вас будет 0.25 медленных попыток перед быстрой попыткой. Затем безразлично, закончите ли вы второй уровень быстро или медленно. Ожидаемое время равно 0.25·30 + 20 + 0.85·3 + 0.15·9 = 31.4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 8
2 8 81
|
3.14
|
|
2
|
2 30
20 30 80
3 9 85
|
31.4
|
|
3
|
4 319
63 79 89
79 97 91
75 87 88
75 90 83
|
314.159265358
|