Microbe Experiment (Bug Party)

Have you heard of Just Odd Inventions Inc. (JOI for short)? Its business is to make "just odd inventions." One of its projects is to trap many microbes alive in a single petri dish.

There are $N$ microbes under study, numbered $1, 2, \dots, N$. When a microbe is trapped in the dish, it instantly releases a harmful substance called foo (fatally odd object) into the dish. All foo released by the trapped microbes is absorbed equally by every microbe in the dish. Each microbe has a foo tolerance; if it absorbs more foo than its tolerance, it dies.

Microbe $i$ releases $a_i$ milligrams of foo and tolerates $b_i$ milligrams. That is, if microbes $i_1, i_2, \dots, i_k$ are trapped, each of them absorbs $(a_{i_1} + a_{i_2} + \dots + a_{i_k}) / k$ milligrams of foo, and microbe $i$ dies if this absorbed amount is greater than its tolerance $b_i$.

You must trap as many microbes alive as possible. However, the corpses of dead microbes harm the environment inside the dish, so no microbe in the dish may die from absorbing foo.

Given the number of microbes and each microbe's foo release amount and tolerance, find the maximum number of microbes that can be trapped alive in a single dish.

• The first line contains an integer $N$, the number of microbes under study.
• Each of the next $N$ lines, the $i$-th of them, contains two positive integers $a_i$ and $b_i$ separated by a space, meaning microbe $i$ releases $a_i$ milligrams of foo and tolerates $b_i$ milligrams.

Print, on a single line, the maximum number of microbes that can be trapped alive in one dish.

• $1 \le N \le 300000$ — the number of microbes under study
• $1 \le a_i \le 100000$ — foo released by microbe $i$ (milligrams)
• $1 \le b_i \le 100000$ — foo tolerance of microbe $i$ (milligrams)

Note that the sum of released foo may exceed the range of a 32-bit integer, so use 64-bit integers.

In the sample input (6 microbes), if microbes 2, 4, and 5 are placed in the dish, the total foo released is $5 + 10 + 6 = 21$ milligrams, so each microbe absorbs $21 / 3 = 7$ milligrams. Their tolerances are $9, 12, 7$ milligrams respectively, so none of them dies. Moreover, it is impossible to place 4 or more microbes without any of them dying.