問題文

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

高橋君は $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$ 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

4
5 6
12 4
14 7
21 2

出力例1

23

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

• 競技開始直後に風船 $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$ となり、これが最小値となります。

入力例2

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

出力例2

105