Description

After Cao Chong solved the elephant problem, Cao Cao wanted his son to take on some real work, so he sent him to manage a pig farm in the Central Plains. Cao Chong was unhappy and worked carelessly. One day, Cao Cao wanted to know the number of sows, so Cao Chong decided to play a trick on him. For example, suppose there are $16$ sows. If $3$ pens are built, then $1$ sow has nowhere to go. If $5$ pens are built, there is still $1$ sow with no place to go. If $7$ pens are built, there are $2$ sows left without a place. As Cao Cao’s personal secretary, you must report the exact number of sows. What should you do?

Input Format

The first line contains an integer $n$ — the number of times pens are built. The next $n$ lines each contain two integers $a_i, b_i$, meaning that when $a_i$ pens are built, there are $b_i$ sows without a place to go. You may assume $a_1 \sim a_n$ are pairwise coprime.

Output Format

Output a single positive integer: the minimum possible number of sows that Cao Chong raises.

3
3 1
5 1
7 2

16

Hint

$1 \leq n\le10$，$0 \leq b_i\lt a_i\le100000$，$1 \leq \prod a_i \leq 10^{18}$

Translated by ChatGPT 5