Problem Description

The black cat, Mr. Snuke, is playing a card game called "Pumpkin 2".

Mr. Snuke decided to think about the following problem:

Currently, Mr. Snuke has $ N $ cards in his hand. The cost of the $ i $th card is $ C_i $, and the gain is $ G_i $.

For each card, Mr. Snuke can perform one of the following operations exactly once:

• Extraction: The mana increases by the value of the card's gain. However, Mr. Snuke initially has 0 mana.
• Summon: By consuming mana equal to the value of the card's cost, the card can be summoned. However, summoning cannot be performed if there is not enough mana.

The cards for the operations can be chosen in any order.

At this point, what is the maximum number of cards that Mr. Snuke can summon?

Input Format

The input is given from the standard input in the following format:

$ N $ $ C_1 $ $ G_1 $ $ C_2 $ $ G_2 $ $ : $ $ C_N $ $ G_N $

Output Format

Output the maximum number of cards that Mr. Snuke can summon.

Sample Input and Output

Sample Input #1

5
3 0
0 4
2 1
2 0
1 3

Sample Output #1

3

Sample Input #2

7
1 0
2 1
3 1
3 2
3 2
4 0
5 5

Sample Output #2

3

Sample Input #3

1
1 0

Sample Output #3

0

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $0 \leq C_i \leq 10^9$
• $0 \leq G_i \leq 10^9$

Sample Explanation 1

For example, the following operations can be performed to summon 3 cards:
- Extract the 5th card. Mana increases to 3.
- Summon the 3rd card. Mana decreases to 1.
- Extract the 2nd card. Mana increases to 5.
- Summon the 1st card. Mana decreases to 2.
- Summon the 4th card. Mana decreases to 0.

Sample Explanation 3

In this input, no cards can be summoned.

见题面 Input 部分

见题面 Output 部分