配点 : $700$ 点

問題文

ある年のCODE FESTIVALの本戦には $N$ 人の参加者が集まりました。 参加者 $i$ は身長が $H_i$ で力が $P_i$ です。

りんごさんは参加者に座布団を積むゲームをしてもらおうとしています。

参加者は好きな順番で並び、$1$ 人ずつ座布団を $1$ 箇所に積んでいきます。 はじめ、座布団は $1$ 枚も積まれていません。 参加者 $i$ は、自分の番が回ってきた時にすでに積まれた座布団が $H_i$ 枚以下の場合はちょうど $P_i$ 枚の座布団を積みます。そうでない場合は諦めて $1$ 枚も積みません。

りんごさんはできるだけ多くの参加者に座布団を積んで欲しいと思っています。 参加者の並び順を工夫することによって、最大で何人の参加者に座布団を積んでもらうことができるでしょうか？

制約

• $1 \leq N \leq 5000$
• $0 \leq H_i \leq 10^9$
• $1 \leq P_i \leq 10^9$

入力

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

$N$

$H_1$ $P_1$

$H_2$ $P_2$

$:$

$H_N$ $P_N$

出力

座布団を積む参加者の人数の最大値を出力せよ。

3
0 2
1 3
3 4

2

入力の通りの順に参加者が並ぶと、$1,3$ 番目の参加者が座布団を積むことができます。

また、$3$ 人全員が座布団を積めるような並び順は存在しないため、答えは $2$ 人となります。

3
2 4
3 1
4 1

3

$2$ 番、$3$ 番、$1$ 番の順で参加者が並ぶと、全員が座布団を積むことができます。

10
1 3
8 4
8 3
9 1
6 4
2 3
4 2
9 2
8 3
0 1

5