You are given ~N~ projects. Each project takes a certain number of days to complete and has a deadline.

You may work on at most one project at a time, and once you start a project, you must finish it without interruption. All projects are available from day ~1~.

Your goal is to choose a subset of projects and an execution order so that:

• every chosen project is completed on or before its deadline
• the number of chosen projects is as large as possible

Input Format

The first line contains a single integer ~N~.

Each of the next ~N~ lines contains two integers ~t_i~ and ~d_i~:

• ~t_i~: the number of days needed for project ~i~
• ~d_i~: the deadline of project ~i~

Output Format

Print a single integer: the maximum number of projects that can be completed on time.

Example

Input

5
4 7
2 4
3 6
1 5
5 9

Output

3

Explanation

A valid optimal schedule is:

• ~2, 4~
• ~1, 5~
• ~4, 7~

The total completion times are ~2, 3, 7~, all within their deadlines.

Constraints

• ~1 ≤ N ≤ 200000~
• ~1 ≤ t_i ≤ 10^9~
• ~1 ≤ d_i ≤ 10^9~

Subtasks

• 50% of the tests satisfy ~N ≤ 2000~.
• 50% of the tests use the full constraints.