Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Maximum Meetings

By Muhimin_Osim · 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.

Discussion

Statistics


48% Solution Ratio

YouKnowWhoEarliest, 3w ago

Cyber_WizardFastest, 0.1s

sabertoothLightest, 1.7 MB

al.nomanShortest, 711B

Submit

Login to submit

Editorial

This problem is pretty straight forward. All you need to do is to check at each time starting from 1... Read more...

Related Contests

Criterion 2020 Round 4 Ended at 2020-03-13 11:30:00 +0000 UTC