The shorties decided to take Dunno or Donut on a flight to the moon. Unable to reach an agreement, they decided to vote. Dunno and Donut watch the voting summary. The Shorties show Dunno and Donut the ratio of the current number of votes received by Dunno and Donut, but not the actual number of votes. Dunno and Donut looked at the report
N times, and when they looked at it the
i (1<=i<=N) times, the ratio was
Pi:Ni. Dunno and Donut are known to have had at least one vote when they first saw the report. Find the minimum possible total number of votes Dunno and Donut received when they checked the report for the
Nth time. It can be assumed that the number of votes received by Dunno and Donut never decreases.
Input
The first line specifies an integer
N (1<=N<=1000). The following
N lines contain 2 numbers each
Pi and
Ni ;(1<=P
i,N
i<=1000).
Pi and
Ni are relatively prime numbers.
Imprint
Output the minimum possible total number of votes. It is guaranteed that the correct answer is no more than 10
18.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3
23
1 1
3 2 |
10 |
The number of votes received by Donut and Dunno changes as follows: 2.3 → 3.3 → 6.4.
The total number of votes at the end is 10, which is the lowest possible number. |
| 2 |
4
1 1
1 1
15
1 100
| 101 |
It's possible that neither Donut nor Dunno got votes between the time they viewed the report and the next time they viewed it. |
| 3 |
5
3 10
48 17
31 199
231 23
3 2 |
6930 |
|