#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Title

### Problem Statement

There are an integer sequence `A _{1},...,A_{N}` consisting of

`N`terms, and

`N`buttons. When the

`i`-th

`(1 ≦ i ≦ N)`button is pressed, the values of the

`i`terms from the first through the

`i`-th are all incremented by

`1`.

There is also another integer sequence `B _{1},...,B_{N}`. Takahashi will push the buttons some number of times so that for every

`i`,

`A`will be a multiple of

_{i}`B`.

_{i}Find the minimum number of times Takahashi will press the buttons.

### Constraints

- All input values are integers.
`1 ≦ N ≦ 10`^{5}`0 ≦ A`_{i}≦ 10^{9}(1 ≦ i ≦ N)`1 ≦ B`_{i}≦ 10^{9}(1 ≦ i ≦ N)

### Input

The input is given from Standard Input in the following format:

NA_{1}B:_{1}A_{N}B_{N}

### Output

Print an integer representing the minimum number of times Takahashi will press the buttons.

### Sample Input 1

3 3 5 2 7 9 4

### Sample Output 1

7

Press the first button twice, the second button twice and the third button three times.

### Sample Input 2

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

### Sample Output 2

22

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 16 | 1s | 256MB | Minimum |

2 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o 2array -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512