Circuits

Interview

Time limit1sMemory limit128 MB

Summary

Pick the most cables whose total battery voltage does not exceed their total wire tolerance.

Level: Easy3 of 10
Topics: Sorting, Greedy, Prefix sum
Solved: No attempts yet

Problem

For his birthday, Jaś received a set of magical electric cables. Each cable consists of one wire and one battery. The $i$ -th wire can withstand a voltage of $d_i$ volts, and the $i$ -th battery supplies a voltage of $b_i$ volts.

Jaś builds circuits from the cables: he picks some cables, twists their wires together into a single thicker wire, and bends that wire into a loop. The voltage across the loop equals the sum of the voltages of all the chosen batteries, and the twisted wire can withstand a voltage equal to the sum of the voltages that the individual wires can withstand.

A loop burns out if the voltage across it exceeds what the wire can withstand. Jaś wants to build a loop that does not burn out, so the sum of the chosen battery voltages must not exceed the sum of the chosen wire tolerances. What is the greatest number of cables the loop can consist of?

Input

The first line contains a single integer $n$ ( $1 \le n \le 500\,000$ ), the number of cables. Each of the next $n$ lines contains two integers $d_i$ , $b_i$ ( $0 \le d_i, b_i \le 10^6$ ) describing one cable.

Output

Print a single integer: the maximum number of cables that can form a loop which does not burn out.

Examples2

Example 1
Input
```
2
2 2
2 2
```
Expected output
```
2
```
Example 2
Input
```
1
5 3
```
Expected output
```
1
```