[AGC009A] Multiple Array

## 题目描述 有一个 $ 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 $ 次。

[problemUrl]: https://atcoder.jp/contests/jrex2017/tasks/agc009_a $ 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 $

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

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 $ 回押せばよいです。