AT_abc023_d [ABC023D] 射撃王

高桥最近正在练习射击。 他参加了一个射击比赛，比赛内容是射击气球，让自己得到的分数尽量小。 气球从1到N依次编号。每个气球都有一个起始高度Hi，每个气球每秒可以升高的高度为Si。 高桥开始时可以先打掉一个气球，随后每一秒他可以射击一次。当他打掉气球后，所得的分数就是气球的高度。而最终的的得分就是这些分数中的一个最大值。 高桥想知道他自己能得到的尽量小的分数是多少，来判断自己是否真的是一个菜鸡。

第一行为气球的个数N（1 ≦ N ≦ 100,000） 下面N+1行，每行两个整数Hi和Si，表示气球的初始高度和气球的升高速度。 (1 ≦ Hi,Si ≦ 1,000,000,000) 输入数据保证气球的高度只会增加而不会下降

输出一个数，表示高桥能拿到的最小分数

### 部分点 この問題には部分点が設定されている。 - $ 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 $ となり、これが最小値となります。