問題文

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

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

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

制約

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

入力

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

$N$ $A_1$ $B_1$ : $A_N$ $B_N$

出力

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

入力例 1

3
3 5
2 7
9 4

出力例 1

7

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

入力例 2

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

出力例 2

22