Course Registration

Time limit1sMemory limit1024 MB

Summary

Given N courses with seat capacities a_i and interested-student counts b_i, find how many courses Dalgu can take under the best priority order against the worst registration order.

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

Problem

Dalgu looked over the courses offered this semester and narrowed the list to $N$ courses he wants to take. Ambitious as he is, Dalgu wants to take as many of them as possible this semester, so he surveyed each of the $N$ courses for its enrollment capacity and the number of students who want to take it. Course $i$ has a capacity of $a_i$ seats, and $b_i$ students, including Dalgu, want to take it. The school has $M$ students in total, including Dalgu, and each student can register for at most one course per second. If several students try to register for the same course at the same moment, Dalgu can always register for that course first. Registration is first come, first served, and a course that is full cannot accept more registrations. Students other than those Dalgu surveyed do not register for that course. Before registration begins, Dalgu assigns each of the $N$ courses a distinct priority and plans to register in priority order. If a higher-priority course is already full, he skips it and tries the next priority. He cannot change the priorities once registration has started. The order in which other students register changes how many courses Dalgu can get, sometimes by a lot. So Dalgu wants to choose the priorities that let him take the most courses even in the worst possible order of the other students' registrations. Given the best priority assignment for Dalgu, find the number of courses he can take in the worst case.

Input

The first line contains two integers $N$ and $M$ , separated by a space, where $N$ is the number of courses Dalgu wants to take and $M$ is the total number of students, including Dalgu. $(1 \leq N, M \leq 100000)$ Each of the next $N$ lines contains two integers $a_i$ and $b_i$ , separated by a space, where $a_i$ is the capacity of the $i$ -th course and $b_i$ is the number of students, including Dalgu, who want to take it. $(1 \leq a_i, b_i \leq M)$

Output

Print the number of courses Dalgu can take in the worst case, when the priorities are assigned in the way that maximizes this number.

Examples3

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