東京大学プログラミングコンテスト2012

E - 選挙


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

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

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


入力

n
a_1 b_1
...
a_n b_n

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

出力

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

制約

部分点

この問題の判定には,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

Submit提出する