Maximum Meetings

Muhimin_Osim Criterion 2020 Round 4
Limits 1s, 256 MB

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

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).

Output

Print a single integer, denoting the maximum number of meetings that can be held by the employees.

Sample

InputOutput
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.

Submit

Login to submit.

Statistics

55% Solution Ratio
YouKnowWhoEarliest, Mar '20
Cyber_WizardFastest, 0.1s
Fizzz_83Lightest, 1.6 MB
al.nomanShortest, 711B
Toph uses cookies. By continuing you agree to our Cookie Policy.