题目描述

给定由 $N$ 个项组成的整数序列 $A_1,...,A_N$，以及 $N$ 个按钮。当按下第 $i$ 个按钮（$1 ≤ i ≤ N$）时，从头到第 $i$ 个项的值都会增加 $1$。

还有另一个整数序列 $B_1,...,B_N$。Takahashi 将按下按钮多次，使得对于每个 $i$，$A_i$ 是 $B_i$ 的倍数。

找出 Takahashi 按下按钮的最小次数。

约束条件

• 所有输入值都是整数。
• $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$

输出

打印一个整数，表示 Takahashi 按下按钮的最小次数。

示例 1

3
3 5
2 7
9 4

输出 1

7

按下第一个按钮两次，第二个按钮两次，第三个按钮三次。

示例 2

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

输出 2

22