题目描述

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

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

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

输入格式

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

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

输出格式

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

题目大意

题目描述

有一个 $N$ 项的数列 $A_1, \dots ,A_N$ 和 $N$ 个按钮。如果按下第 $i(1 \leq i \leq N)$ 个按钮，数列 $A$ 从第 $1$ 项到第 $i$ 项的值将各增加 $1$ 。

给出数列 $B_1, \dots ,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
A1 B1
:
AN BN

输出

输出一个数字，表示高桥君按按钮的最小次数。（行末换行）

样例

样例见原题面，另：样例1~2与样例3~4重复。

样例1解释

按第一个按钮 $2$ 次，第二个按钮 $2$ 次，第三个按钮 $3$ 次。

3
3 5
2 7
9 4

7

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

22

提示

制約

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

Sample Explanation 1

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