Reference: LeetCode 630 — Course Schedule III

There are ~n~ courses. Course ~i~ requires ~duration_i~ consecutive days to complete and must be finished no later than day ~lastDay_i~.

You begin studying on day ~1~. Only one course may be studied at a time, and once a course is started, it must be studied continuously until completion.

You may choose any subset of courses and arrange the chosen courses in any order.

Find the maximum number of courses that can be completed before their respective deadlines.

Input

• The first line contains one integer ~n~.
• Each of the next ~n~ lines contains two integers: ~duration_i~ and ~lastDay_i~.

Output

• Print one integer: the maximum number of courses that can be completed.

Constraints

• ~1 \le n \le 10^4~
• ~1 \le duration_i \le 10^4~
• ~1 \le lastDay_i \le 10^4~

Example 1

Input:

4
100 200
200 1300
1000 1250
2000 3200

Output:

3