[ABC023D] 射撃王

# 题目描述 高桥最近正在练习射击。 他参加了一个射击比赛，比赛内容是射击气球，让自己得到的分数尽量小。 气球从1到N依次编号。每个气球都有一个起始高度Hi，每个气球每秒可以升高的高度为Si。 高桥开始时可以先打掉一个气球，随后每一秒他可以射击一次。当他打掉气球后，所得的分数就是气球的高度。而最终的的得分就是这些分数中的一个最大值。 高桥想知道他自己能得到的尽量小的分数是多少，来判断自己是否真的是一个菜鸡。 # 输入格式 第一行为气球的个数N（1 ≦ N ≦ 100,000） 下面N+1行，每行两个整数Hi和Si，表示气球的初始高度和气球的升高速度。 (1 ≦ Hi,Si ≦ 1,000,000,000) 输入数据保证气球的高度只会增加而不会下降 # 输出格式 输出一个数，表示高桥能拿到的最小分数

[problemUrl]: https://atcoder.jp/contests/abc023/tasks/abc023_d 高橋君は最近、射撃にハマっている。 高橋君は $ 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 $ ずつ上昇していくことを表す。

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

4
5 6
12 4
14 7
21 2

23

6
100 1
100 1
100 1
100 1
100 1
1 30

105

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 50 $ かつ $ H_i\ ≦\ 100,000 $ かつ $ S_i\ ≦\ 2,000 $ を満たすデータセット $ 1 $ に正解した場合は、$ 30 $ 点が与えられる。 - 追加制約のないデータセット $ 2 $ に正解した場合は、上記とは別に $ 70 $ 点が与えられる。 ### Sample Explanation 1 例えば、以下に示す順番で風船を割ります。 - 競技開始直後に風船 $ 3 $ を割ります。風船 $ 3 $ のペナルティは $ 14\ +\ 7\ ×\ 0\ =\ 14 $ です。 - 競技開始から $ 1 $ 秒後に風船 $ 4 $ を割ります。風船 $ 4 $ のペナルティは $ 21\ +\ 2\ ×\ 1\ =\ 23 $ です。 - 競技開始から $ 2 $ 秒後に風船 $ 2 $ を割ります。風船 $ 2 $ のペナルティは $ 12\ +\ 4\ ×\ 2\ =\ 20 $ です。 - 競技開始から $ 3 $ 秒後に風船 $ 1 $ を割ります。風船 $ 1 $ のペナルティは $ 5\ +\ 6\ ×\ 3\ =\ 23 $ です。 以上より高橋君の得点は $ 23 $ となり、これが最小値となります。