Maximum House Robbery with Canceled Hostility

You are a master thief planning heists in a town with n households. For each household i, you have three options:

1. Steal the money: you take m_i dollars from the house. However, this action makes that household hostile toward you.
2. Pay the household: you give the household p_i dollars, and in return the household helps you by canceling the hostility of one household from which you previously stole.
3. Do nothing.

You start with $0$ dollars and you are free to visit the households in any order. In the end, you must have no household hostile toward you (i.e. every theft must be "canceled" by a distinct pay action) and your money must never be negative. Under these conditions, what is the maximum number of households from which you can steal?

Note: When you choose to pay in a household, that payment can cancel the hostility from any one of the houses you have stolen from (each pay cancels exactly one theft). The operations may be performed in any order as long as at the time of a pay action there is at least one previous theft whose hostility has not yet been canceled, and your money balance remains non‐negative throughout the process.

Formally, suppose you select a set T of households to steal from and a disjoint set P of households to pay such that |T| = |P| = k. If you perform all the theft actions first (in any order) and then the pay actions (in an order sorted by increasing p_i values), you must have for every 1 ≤ j ≤ k:

where \(m_{t_i}\) are the amounts from theft actions sorted in non‐increasing order and \(p_{p_i}\) are the payment costs sorted in non‐decreasing order. Your task is to choose the operations (each household can be used at most once, and you must choose exactly one option per household) to maximize k.

inputFormat

The first line contains a single integer n (the number of households). Each of the next n lines contains two integers m_i and p_i separated by a space, indicating the amount you would steal and the amount you would pay for household i, respectively.

outputFormat

Output a single integer—the maximum number of households you can steal from such that, by ordering the operations optimally, you can end with a non‐negative amount of money and no household holding hostility against you.

sample

3
5 3
2 2
4 5

1