Have you heard of a company called Just Odd Inventions? This company specializes just in odd inventions. We will call it JOI Corp for short.
JOI Corp has N employees, numbered from 1 to N. The office hours of JOI corp are from time 0 to time M. At time 0 and at time M, all employees are required to be in the office.
Today, for some reason, each employee will make exactly one trip out of the office. Employee i (1 ≤ i ≤ N) will leave the office at time Si and return to the office at time Ti. No two employees will leave or return at the exact same time.
There is only one huge door that serves as an entrance to JOI Corp. The employees of JOI Corp can use this door to enter or leave the office. There is a lock on the door. The door can either be locked or unlocked. Employees in the office can lock or unlock the door easily. However, employees outside the office must have a key with them in order to open the door if it is locked. At time 0, the door is locked.
Each employee must be able to enter the company when he or she returns to the office. In other words, for all i (1 ≤ i ≤ N), if employee i returns to the office at time Ti and the door is locked at time Ti, employee i must have at least one key. After an employee returns to the office, or after an employee with a key leaves the office, the employee can choose to either leave the door unlocked or lock it. Employees without a key cannot lock the door after leaving the office.
The president of JOI Corp will distribute K duplicate keys among the N employees. In order to reduce the risk of losing keys, giving one employee multiple duplicate keys is not allowed. Moreover, the president emphasizes efficiency during office hours. Hence, employees can only lock or unlock the door when they are about to leave or return to the office, and at no other point in time.
For security reasons, JOI Corp wants to maximize the total duration of all time periods between time 0 and time M during which the door is locked.
Given all the exit and entry times of the employees and the number of duplicate keys that will be distributed to the N employees, find the maximum total duration that the door can be locked for between time 0 and time M, assuming that the distribution of the keys and the locking and unlocking of the doors is managed as well as possible.
Input
Read from standard input.
- On the first line, there are three integers, N, M and K. This means that JOI Corp has N employees and opens from time 0 to time M. Also, K duplicate keys will be distributed to the N employees.
- On the ith line of the next N lines, there are two integers, Si and Ti. This means employee i will leave the office at time Si and return to the office at time Ti.
Output
Print one line containing one integer to standard output. The integer should be the maximum total duration of time that the door can stay locked within time 0 and time M.
Constraints
All test cases satisfy the following constraints.
- 1 ≤ N ≤ 2 000.
- 1 ≤ M ≤ 1 000 000 000.
- 1 ≤ K < N.
- 0 < Si < Ti < M (1 ≤ i ≤ N).
- For any i, j (1 ≤ i ≤ N, 1 ≤ j ≤ N, i ≠ j), Si ≠ Sj, Si ≠ Tj, Ti ≠ Tj.
Subtasks
Subtask 1 (10 points):
The following constraints are satisfied.
Subtask 2 (90 points):
No further constraints.
Sample Input 1
4 20 2
3 11
5 15
6 10
12 18
Sample Output 1
13
Explanation
In this test case, there are 4 employees, and we can distribute a key to 2 of them. If we distribute the key to employees 2 and 4, then following the method below, the maximum total duration that the door can be locked is 13.
- At time 0, the door is locked.
- At time 3, employee 1 leaves the office. Since employee 1 does not have a key, the door is left unlocked.
- At time 5, employee 2 leaves the office and locks the door.
- At time 6, employee 3 leaves the office. Since employee 3 does not have a key, the door is left unlocked.
- At time 10, employee 3 returns to the office and leaves the door unlocked.
- At time 11, employee 1 returns to the office and locks the door.
- At time 12, employee 4 leaves the office and locks the door.
- At time 15, employee 2 returns to the office and locks the door.
- At time 18, employee 4 returns to the office and locks the door.
- At time 20, the door is locked.
Since the total duration of time that the door was locked during the period of time from time 0 to time 20 is 13, the output is 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