题目描述

有一个包含 $N$ 项的数列 $A_1,\ldots,A_N$，以及 $N$ 个按钮。按下第 $i$ 个按钮（$1 \leq i \leq N$）时，数列 $A$ 的第 $1$ 项到第 $i$ 项的值都会增加 $1$。

现在给定一个数列 $B_1,\ldots,B_N$。高桥君希望通过多次按按钮，使得对于所有的 $i$，$A_i$ 都变成 $B_i$ 的倍数。

请你求出高桥君最少需要按按钮的次数。

输入格式

输入通过标准输入给出，格式如下：

$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$

输出格式

输出一个整数，表示高桥君最少需要按按钮的次数。

样例 1

输入

3
3 5
2 7
9 4

输出

7

样例 2

输入

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

输出

22

说明/提示

限制条件

• 所有输入均为整数。
• $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)$

样例解释 1

按第 $1$ 个按钮 $2$ 次，第 $2$ 个按钮 $2$ 次，第 $3$ 个按钮 $3$ 次即可。

由 ChatGPT 4.1 翻译