Мосты
В стране Лемурия имеется N островов, соединенных мостами. Между каждыми двумя островами с номерами i и i+1 (1 ≤ i ≤ N-1) имеется несколько параллельных мостов. Среди них в точности a_i мостов являются устойчивыми, а остальные b_i мостов такими не являются. Если человек проходит по устойчивому мосту, ведущего из острова i, то он попадает на остров i+1. Но если двигаться по неустойчивому мосту, то еще до достижения противоположного края мост ломается (и поскольку мост уже сломан, то далее в задаче он уже не рассматривается), и путник падает в реку, а течение сносит его к острову номер 1.
Вы находитесь на острове номер 1. Вам следует перебраться на остров номер N. Воспользуемся следующей стратегией: на каждом шаге случайным образом выбираем мост, ведущий из текущего острова на следующий, который еще не сломан, и двигаемся по нем. Если a_i > 0 для всех i, то мы когда-нибудь достигнем цели.
Длина каждого моста равна 1. Найдите среднее расстояние, которое Вы пройдете по мостам прежде чем достигнете острова с номером N если будете придерживаться выше описанного алгоритма.
Входные данные
Первая строка содержит целое число N (1 ≤ N ≤ 1000). Следующие N-1 строк содержат описание мостов. i-ая строка содержит два целых числа a_i и b_i (1 ≤ a_i ≤ 1000, 0 ≤ b_i ≤ 1000), разделенные одним пробелом. Количество неустойчивых мостов не более 1000.
Выходные данные
Вывести одно вещественное число - ответ на задачу. Абсолютная или относительная погрешность ответа должна быть меньше 10^{-9}.