You are given a list of tasks. Each task is represented by two integers:

[id, deadline]

where:

• id is the type/ID of the task.
• deadline is the latest time by which the task must be completed.

Each task takes 1 unit of time to complete.

You are also given an integer cooldown.

Your goal is to complete the maximum possible number of tasks while satisfying all deadlines and the following cooldown rule.

Cooldown Rule

Consider two consecutively completed tasks:

• If their IDs are different, the next task can be completed immediately.
• If their IDs are the same, a cooldown of cooldown units must be applied before another task with the same ID can be completed.

You may choose the order in which tasks are executed, and you are not required to complete every task.

A task can only be completed if its completion time does not exceed its deadline.

Return the maximum number of tasks that can be completed.

Input Format

• The first line contains an integer N, the number of tasks.
• The next N lines contain two integers id and deadline, representing each task.
• The last line contains an integer cooldown.

Output Format

Print a single integer representing the maximum number of tasks that can be completed.

Example

Input

5
1 2
1 5
2 2
2 4
1 7
1

Output

4

Explanation

A valid ordering can be constructed by alternating task IDs whenever possible.

For example:

Task ID: 1 → 2 → 1 → 2

Since consecutive tasks have different IDs, no cooldown is required between them.

The selected tasks can all be completed within their respective deadlines, giving a maximum of 4 completed tasks.

Constraints

• 1 ≤ N ≤ 2 × 10^5
• 1 ≤ id ≤ 10^9
• 1 ≤ deadline ≤ 10^9
• 0 ≤ cooldown ≤ 10^9