Pizza for the Party

Time limit2sMemory limit1024 MB

Summary

Given N pizzas, each with heating time a_i and hot time b_i on one microwave, find the most pizzas that can be hot at the same instant.

Level: Medium7 of 10
Topics: Greedy, Sorting, Heap
Solved: No attempts yet

Problem

Early March, and Veniamin, a first-year student at NUOP (Unknown University of Olympiad Programming), has already finished his exams. That is reason enough for a party.

Veniamin picked a day and time, invited all his friends, and ordered a huge amount of pizza. Then the pizza arrived much earlier than planned. The pizza will be cold by the time the friends arrive, so the reheating order needs to be planned in advance. Scheduling theory is taught at NUOP only in the third year, so Veniamin asks you for help. The task is stated as follows:

Veniamin has $N$ pizzas.
His goal is to choose the order in which pizzas are heated in the microwave so that at some moment as many pizzas as possible are hot.
Each pizza $i$ $i$ is described by two values, $a_i$ $a_{i}$ and $b_i$ $b_{i}$ .
- $a_i$ is the number of seconds needed to heat pizza $i$ in the microwave.
- $b_i$ is the number of seconds pizza $i$ stays hot.
To become hot, a pizza must stay in the microwave for exactly $a_i$ seconds without interruption.
There is only one microwave, and at most one pizza can be in it at any moment.
All microwave actions (turning it on or off, taking a pizza out, putting one in) happen instantly.
Eating a pizza also happens instantly. The goal is to have the maximum number of pizzas hot at one moment. That moment does not need to last for any positive length of time.

Input

The first line contains an integer $N$ , the number of pizzas ( $1 \le N \le 300000$ ). Each of the next $N$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le 10^9$ ).

Output

Print one number, the maximum number of pizzas that can be hot at the same time.

Hint

Let us look at the first test in more detail.

At time 0, Veniamin puts the first pizza in the microwave.
At time 1, Veniamin takes the first pizza out and puts the second one in.
At time 2, Veniamin takes the second pizza out. At this moment the first pizza is still hot, so the answer is 2. Both pizzas are hot only at this moment. In this example it is impossible to keep both hot for a period of nonzero length.

Examples2

Example 1
Input
```
2
1 1
1 1
```
Expected output
```
2
```
Example 2
Input
```
4
2 12
10 8
7 5
5 1
```
Expected output
```
3
```