Коротышки решили взять в полет на Луну либо Незнайку либо Пончика. Не сумев договориться, они решили проголосовать. Незнайка и Пончик наблюдают краткий отчет о голосовании. Коротышки показывают Незнайке и Пончику соотношение текущего количества голосов, полученных Незнайкой и Пончиком, но не фактическое количество голосов. Незнайка и Пончик посмотрели отчет
N раз, и когда они смотрели его в
i-й (1<=i<=N) раз, соотношение было
Pi:Ni. Известно, что Незнайка и Пончик имели хотя бы один голос, когда впервые увидели отчет. Найдите минимально возможное общее количество голосов, полученных Незнайкой и Пончиком, когда они проверили отчет в
N-й раз. Можно предположить, что количество голосов, полученных Незнайкой и Пончиком, никогда не уменьшается.
Входные данные
В первой строке задается целое число
N (1<=N<=1000). В следующих
N строках записано по 2 числа
Pi и
Ni (1<=P
i,N
i<=1000).
Pi и
Ni - взаимно простые числа.
Выходные данные
Выведите минимально возможное общее количество голосов. Гарантируется, что правильный ответ - не более 10
18.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
3
2 3
1 1
3 2 |
10 |
Количество голосов, полученных Пончиком и Незнайкой, изменяется так 2,3 → 3,3 → 6,4.
Общее количество голосов в конце составляет 10, что является минимально возможным числом. |
| 2 |
4
1 1
1 1
1 5
1 100 |
101 |
Возможно, что ни Пончик ни Незнайка не получили голосов между моментом, когда они смотрели отчет, и моментом, когда они смотрели его в следующий раз. |
| 3 |
5
3 10
48 17
31 199
231 23
3 2 |
6930 |
|