I am the boss of my company. I have n employees. The office time of my company starts at 1. Every employee has his own working period. From the starting of the office time, whenever at a time, exactly k employees have at least t unit time (inclusive) common to their working periods, they immediately start a meeting and an employee can participate in at most 1 meeting. A meeting doesn't need a time interval. So, common time interval t is only for the criteria to start a meeting.
Now, I wonder what is the maximum number of meetings that can be held by all the employees. So, I hired you to do this task.
Input starts with three integers n, k, t (1 ≤ n,k,t ≤ 2*105), denoting the number of employees, the number of employees needed for a meeting and the minimum length of a meeting.
Each of the following n lines contains two integers l and r (1 ≤ l ≤ r ≤ 2*105), denoting the time interval of the working period of an employee (inclusive).
Print a single integer, denoting the maximum number of meetings that can be held by the employees.
Input | Output |
---|---|
5 2 2 1 3 2 4 1 5 2 9 7 9 | 2 |
When we are at time 2, there are 2 employees available.
1 - 5
1 - 3
Participant 1,3 start a meeting.
When we are at time 3, there are 2 more employees available for a meeting.
2 - 4
2 - 9
Participant 2,4 start a meeting.
Participant 5 can not attend any meeting.