問題

CAT 国では今日、議会の総選挙が行われた。CAT 国の選挙は比例代表制のみを採用するという変わった形式をとっており、議席は得票数に応じて最大剰余方式で分配される。すなわち、 n 個ある政党それぞれの得票数を a_1, a_2, ..., a_n, 総票数を s = a_1 + a_2 + ... + a_n, 総議席数を m としたとき、まずそれぞれの政党に議席が [\frac{a_i}{s}m] ずつ割り当てられ、残った議席は \frac{a_i}{s}m の小数部が大きい政党から順(同点の場合は番号の小さい政党優先)に1席ずつ配られる。ここで，[x]は小数xの整数部分を表す．

CAT 国に住むあなたはもちろん投票に行き、今はチャットで選挙の結果について友人と話しているところである。友人は次のような情報を教えてくれた:

• 各党はそれぞれ a_1, a_2, ..., a_n 票を獲得した。
• 各党はそれぞれ少なくとも b_1, b_2, ..., b_n 議席を獲得した。

彼の情報が正しいとしたとき、総議席数 m の取りうる値の中で最小のものを求めよ。

---

入力

n
a_1 b_1
...
a_n b_n

1 行目に政党数 n が与えられる. 続く n 行に, i 番目の政党の得票数 a_i, i 番目の政党が少なくとも獲得した議席の数 b_i がこの順で与えられる.

出力

条件を満たす総議席数 m の最小値を1行で出力せよ.

制約

• 1 \leq n \leq 100
• 1 \leq a_i \leq 1000
• 0 \leq b_i \leq 10^9
• b_i \geq 1をみたすiが存在する.

部分点

この問題の判定には，50 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

n, a_i, b_i \leq 50

---

入力例 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