Problem Statement

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

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

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

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

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

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

Input

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

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$ 点が与えられる。

Output

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