Class

Time limit1sMemory limit1024 MB

Summary

Split N students of distinct heights into the fewest teams so that in every team, each student has fewer than k_i taller teammates.

Level: Medium6 of 10
Topics: Greedy, Sorting, Array, Implementation
Solved: No attempts yet

Problem

Professor Kwon Ukje of Soongsil University is preparing a new course. Finding lecturing tiresome, he plans to hand out a team project and coast through the semester by half-listening to presentations. So he wants to split the $N$ students into some number of teams. But the students have strong pride. Student $i$ says that if at least $k_i$ of their teammates are taller than they are, they will storm out of the classroom.

Kind-hearted Professor Kwon Ukje wants to place every student into exactly one team so that every student's demand is satisfied. What is the minimum number of teams he must create?

Input

The first line gives the number of students $N$ .

The next $N$ lines give each student's height $h_i$ and minimum rank $k_i$ .

All students have distinct heights.

Output

Print the minimum number of teams that must be created.

Constraints

$1 \le N \le 500,000$
$1 \le h_i \le 500,000$ , $1 \le k_i \le N$

Examples1

Example 1
Input
```
5
172 1
161 2
188 4
154 2
180 1
```
Expected output
```
3
```