J: エナジードリンク

問題

ixmel、Pulmn 兄弟は $N$ 種類のエナジードリンクをそれぞれ 1 本ずつ持っています。 現在、ixmel と Pulmn のエネルギーはともに 0 で、時刻は午前 0 時です。 ixmel と Pulmn はエネルギーが 0 以下のまま正午になると「たいへんなこと」になります。 エネルギーが正の数では「たいへんなこと」にはなりません。 ixmel とPulmn は「たいへんなこと」にならないために、 毎日朝 6 時に 1 本のエナジードリンクを 2 人で分けて飲むことにしました。 i 番目のエナジードリンクを ixmel が飲むとエネルギーが $a_i$ 増えますが、副作用として 24 時間後にエネルギーが $b_i$ 減ってしまいます。 一方、Pulmn が飲むとエネルギーが $b_i$ 増え、24 時間後にエネルギーが $a_i$ 減ります。 また、ixmel と Pulmn は日が変わった直後、エネルギーは 0 になります。 ixmel と Pulmn は今持っているエナジードリンクだけで、どちらか一方、または両方が「たいへんなこと」になるまでの日数を少しでも長くしたいと思いました。

ixmel、Pulmn 兄弟のために最初にどちらか片方、または両方が「たいへんなこと」になるまでの日数の最大値を求めてください。なお、エナジードリンクを飲む時間は無視できるものとし、「たいへんなこと」が起こる日は求める日数に含まないものとします。

入力

入力は $1+n$ 行からなります。 1 行目には 1 個の整数 $N$ が与えられます。 続く $N$ 行の内、$i$ 行目は 2 個の整数 $a_i, b_i$ が与えられます。

制約

• $1 \le N \le 10^5$
• $1 \le a_i, b_i \le 10^9$

出力

考えられる「たいへんなこと」になるまでの日数の最大値を出力しましょう。 また、末尾に改行を出力しましょう。

サンプル

サンプル入力 1

5
3 5
7 4
11 9
3 7
7 8

サンプル出力 1

4

1 日目から 5 日目に飲むドリンクは、それぞれ 1, 2, 5, 3, 4 とするのが最適です。 各日のエナジードリンクを飲んだあとの (ixmel の体力, Pulmn の体力) は、それぞれ $(3, 5), (2, 1), (1, 3), (3, 2), (-6, -4)$ と変化し、 5 日目に「たいへんなこと」になるので答えは 4 です。

サンプル入力 2

2
1 1
1 1

サンプル出力 2

1

異なる種類で成分が同じエナジードリンクもあります。また、「たいへんなこと」が起こるのは、エネルギーの量が 0 以下の時であることに注意してください。

サンプル入力 2

3
5 9
3 2
7 4

サンプル出力 2

3

4 日目に飲むエナジードリンクはありません。