举行了一场选举。共有 $n$ 个政党参加了此次选举，编号为 $1$ 到 $n$。根据各政党获得的票数，共分配了 $m$ 个席位。席位分配采用以下算法：

假设第 $1, 2, \dots, n$ 个政党分别获得了 $c_1, c_2, \dots, c_n$ 票。令 $s = c_1 + c_2 + \dots + c_n$。首先，对于每个 $i$，向第 $i$ 个政党分配 $\lfloor \frac{c_i}{s} \cdot m \rfloor$ 个席位。然后，将剩余的席位依次分配给 $\frac{c_i}{s} \cdot m$ 的小数部分较大的政党，每个政党分配一个席位。如果小数部分相同，则编号较小的政党优先。

已知以下信息： 第 $1, 2, \dots, n$ 个政党分别恰好获得了 $a_1, a_2, \dots, a_n$ 票。 第 $1, 2, \dots, n$ 个政党分别至少获得了 $b_1, b_2, \dots, b_n$ 个席位。

计算总席位数 $m$ 的最小值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100$)。接下来 $n$ 行，每行包含一对整数 $a_i$ 和 $b_i$ ($1 \le a_i \le 1000, 0 \le b_i \le 10^9$)。你可以假设至少存在一个 $i$ 使得 $b_i \ge 1$。

输出格式

输出总席位数 $m$ 的最小值。

样例

样例输入 1

3
1 2
4 5
2 3

样例输出 1

11

样例输入 2

4
1 0
6 5
4 4
5 8

样例输出 2

25

样例输入 3

1
42 42

样例输出 3

42