Keys (Translated)

JOI Spring Training Camp 2014/15
Original Statement / Submission Site

Problem Statement

Just Odd Inventions (JOI) company has N employees numbered from 1 to N. Each employee works from time 0 to M. At time 0 and time M, all employees must be inside the company.

Today, each employee wants to go outside exactly once. Employee i (1 ≤ i ≤ N) leaves the office at time Si and returns at time Ti. No two employees leave or return at the same time.

There is one door where employees can enter and exit. The door has a lock that can be either locked or unlocked. From inside, anyone can operate the lock. From outside, only employees with a key can operate the lock. At time 0, the door is locked.

Each employee must be able to enter the company when he returns. That is, for each i (1 ≤ i ≤ N), either the door is unlocked at time Ti, or employee i has a key (or both). When any employee returns or an employee with a key leaves, he can choose to either lock the door or leave it unlocked. But when an employee without a key leaves, he cannot lock the door (as he cannot operate the lock from outside).

The president of JOI will give keys to K out of the N employees. Keys cannot be handed over between employees. Also, due to security concerns, employees can only operate the lock when they themselves are entering or exiting the company.

The president wants the door to be locked for as long as possible for security purposes.

Task

Given the outing times of the employees and the number of keys, determine the maximum total duration during which the door can remain locked.

Input

The input consists of:

• The first line contains three integers N, M, and K – number of employees, duration of work time, and number of keys.
• The following N lines each contain two integers Si and Ti – the leave and return times of employee i.

Output

Print a single integer – maximum total time the door can remain locked during work time.

Constraints

• 1 ≤ N ≤ 2000
• 1 ≤ M ≤ 1,000,000,000
• 1 ≤ K < N
• 0 < Si < Ti < M (1 ≤ i ≤ N)
• Si ≠ Sj; Si ≠ Tj; Ti ≠ Tj for any different i, j

Subtasks

• Subtask 1 [10 points]: N ≤ 20, M ≤ 1,000,000
• Subtask 2 [90 points]: No additional constraints

Sample Input 1

4 20 2
3 11
5 15
6 10
12 18

Sample Output 1

13

In this case, employees 2 and 4 are given keys. The lock status over time can be managed as follows:

• Time 0: the door is locked.
• Time 3: employee 1 leaves (no key) – cannot lock.
• Time 5: employee 2 leaves (has key) – locks the door.
• Time 6: employee 3 leaves (no key) – cannot lock.
• Time 10: employee 3 returns – leaves door unlocked.
• Time 11: employee 1 returns – locks the door.
• Time 12: employee 4 leaves (has key) – locks the door.
• Time 15: employee 2 returns – locks the door.
• Time 18: employee 4 returns – locks the door.
• Until time 20: door remains locked.

Total time locked = 13.

Sample Input 2

20 100000 8
29930 89724
56133 70462
28063 78568
32483 64351
9410 20176
55809 62944
32450 85190
73536 73966
20452 78868
45458 63484
8286 47425
76018 81622
16736 49308
85383 94641
25100 40002
22158 22821
23508 41781
61709 98882
58110 78431
28448 89247

Sample Output 2

72454