D - Zabuton 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 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

出力

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

入力例 1

3
0 2
1 3
3 4

出力例 1

2

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

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

入力例 2

3
2 4
3 1
4 1

出力例 2

3

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

入力例 3

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

出力例 3

5

Score : 700 points

Problem Statement

In the final of CODE FESTIVAL in some year, there are N participants. The height and power of Participant i is H_i and P_i, respectively.

Ringo is hosting a game of stacking zabuton (cushions).

The participants will line up in a row in some order, and they will in turn try to add zabuton to the stack of zabuton. Initially, the stack is empty. When it is Participant i's turn, if there are H_i or less zabuton already stacked, he/she will add exactly P_i zabuton to the stack. Otherwise, he/she will give up and do nothing.

Ringo wants to maximize the number of participants who can add zabuton to the stack. How many participants can add zabuton to the stack in the optimal order of participants?

Constraints

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

Input

Input is given from Standard Input in the following format:

N
H_1 P_1
H_2 P_2
:
H_N P_N

Output

Print the maximum number of participants who can add zabuton to the stack.

Sample Input 1

3
0 2
1 3
3 4

Sample Output 1

2

When the participants line up in the same order as the input, Participants 1 and 3 will be able to add zabuton.

On the other hand, there is no order such that all three participants can add zabuton. Thus, the answer is 2.

Sample Input 2

3
2 4
3 1
4 1

Sample Output 2

3

When the participants line up in the order 2, 3, 1, all of them will be able to add zabuton.

Sample Input 3

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

Sample Output 3

5