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$ が与えられます。
考えられる「たいへんなこと」になるまでの日数の最大値を出力しましょう。 また、末尾に改行を出力しましょう。
5 3 5 7 4 11 9 3 7 7 8
4
1 日目から 5 日目に飲むドリンクは、それぞれ 1, 2, 5, 3, 4 とするのが最適です。 各日のエナジードリンクを飲んだあとの (ixmel の体力, Pulmn の体力) は、それぞれ $(3, 5), (2, 1), (1, 3), (3, 2), (-6, -4)$ と変化し、 5 日目に「たいへんなこと」になるので答えは 4 です。
2 1 1 1 1
1
異なる種類で成分が同じエナジードリンクもあります。また、「たいへんなこと」が起こるのは、エネルギーの量が 0 以下の時であることに注意してください。
3 5 9 3 2 7 4
3
4 日目に飲むエナジードリンクはありません。