配点 : $300$ 点

問題文

$N$ 項からなる数列 $A_1,...,A_N$ があり、$N$ 個のボタンがあります。 $i(1 \leq i \leq N)$ 個目のボタンを押すと、数列 $A$ の $1$ 項目から $i$ 項目までの値が $1$ ずつ増加します。

数列 $B_1,...,B_N$ が与えられます。高橋君は、これらのボタンを何回か押して、すべての $i$ に対し、$A_i$ が $B_i$ の倍数になるようにします。

高橋君がボタンを押す回数の最小値を求めてください。

制約

• 入力はすべて整数である。
• $1 \leq N \leq 10^5$
• $0 \leq A_i \leq 10^9(1 \leq i \leq N)$
• $1 \leq B_i \leq 10^9(1 \leq i \leq N)$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $B_1$

:

$A_N$ $B_N$

出力

高橋君がボタンを押す回数の最小値を表す整数を出力せよ。

3
3 5
2 7
9 4

7

$1$ つめのボタンを $2$ 回、$2$ つめのボタンを $2$ 回、$3$ つめのボタンを $3$ 回押せばよいです。

7
3 1
4 1
5 9
2 6
5 3
5 8
9 7

22