D - 射撃王

D - 射撃王解説

実行時間制限: 5 sec / メモリ制限: 256 MB

高橋君は最近、射撃にハマっている。

高橋君は N 個の風船すべてを射撃で割り、得られる得点をできるだけ小さくする競技に参加している。

風船には 1 から N までの番号が付けられていて、風船 i (1 ≦ i ≦ N) は競技開始時に高度 H_i のところにあり、1 秒経過するにつれて高度が S_i だけ増加する。

高橋君は競技開始時に 1 個風船を割ることができ、そこから 1 秒ごとに 1 個の風船を割ることができる。どの順番で風船を割るのかは高橋君が自由に決定できる。

どの風船についても、その風船を割ることによるペナルティが発生する。ペナルティはその風船が割られたときの高度と等しい整数値となる。高橋君が最終的に得る得点は N 個の風船のペナルティのうちの最大値となる。

高橋君が得ることのできる得点として考えられる最小値を求めよ。

入力は以下の形式で標準入力から与えられる。

N
H_1 S_1
H_2 S_2
:
H_N S_N

1 行目には、風船の個数を表す整数 N (1 ≦ N ≦ 100,000) が書かれている。
2 行目から N 行には、風船に関する情報が与えられる。N 行のうち i (1 ≦ i ≦ N) 行目には、2 つの整数 H_i (1 ≦ H_i ≦ 1,000,000,000), S_i (1 ≦ S_i ≦ 1,000,000,000) が空白区切りで与えられる。これは、風船 i が競技開始時に高度 H_i にあり、1 秒経過するにつれて高度が S_i ずつ上昇していくことを表す。

この問題には部分点が設定されている。

N ≦ 50 かつ H_i ≦ 100,000 かつ S_i ≦ 2,000 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。

高橋君が得ることのできる得点として考えられる最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

例えば、以下に示す順番で風船を割ります。

以上より高橋君の得点は 23 となり、これが最小値となります。