0516 - 選挙

問題

CAT 国では今日、議会の総選挙が行われた。CAT 国の選挙は比例代表制のみを採用するという変わった形式をとっており、議席は得票数に応じて最大剰余方式で分配される。すなわち、 n 個ある政党それぞれの得票数を a₁,a₂,…,a_n, 総票数を s=a₁+a₂+...+a_n, 総議席数を m としたとき、まずそれぞれの政党に議席が [m(a_i/s)]ずつ割り当てられ、残った議席は m(a_i/s) の小数部が大きい政党から順(同点の場合は番号の小さい政党優先)に1席ずつ配られる。ここで，[x]は小数xの整数部分を表す．
CAT 国に住むあなたはもちろん投票に行き、今はチャットで選挙の結果について友人と話しているところである。友人は次のような情報を教えてくれた:

• 各党はそれぞれ a₁,a₂,…,a_n 票を獲得した。
• 各党はそれぞれ少なくとも b₁,b₂,...,b_n 議席を獲得した。

入力

n
a1 b1
...
an bn

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

出力

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

制約

• 1 ≦ n ≦ 100
• 1 ≦ a_i ≦ 100
• 0 ≦ b_i ≦ 10⁹
• b_i ≧ 1をみたす i が存在する.

---

入出力例

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