
ZOJ Problem Set  3941
Marjar University often hosts Kpop music festival. A Kpop music festival will last several days. During a Kpop festival, there will be a Kpop party every day. Kpop music is very popular all over the world, so there may be more than one Kpop music festival being hosted simultaneously. Edward, the headmaster of Marjar University, is always obsessed with Kpop music. He will be very excited continuously for K days after attending a Kpop music party. More specifically, If he attends a Kpop party in the ith day, he would be very excited from the ith day to the (i + K  1)th day (inclusive). But the excitatory state does not stack. For example, if K is 5 and Edward attended a party in Day 1 and a party in Day 3, he will be very excited only from Day 1 to Day 7. Edward has got the schedule of N Kpop music festivals in Marjar University. Each Kpop music festival lasts one or more days. The ith Kpop festival starts at the S_{i}th day and ends at the E_{i}th day (inclusive). Due to restrictions on the discipline for the headmaster, he can attend at most M Kpop parties. Now he wants to maximize the number of days being excited. Can you help him? InputThere are multiple test cases. The first line of input is an integer T (≤ 1000) indicating the number of test cases. For each test case: The first line contains three integers, N, K and M. The next N lines, each line contains two integers S_{i} and E_{i} (1 ≤ N ≤ 10, 1 ≤ K, M, S_{i}, E_{i} ≤ 10^{9}). OutputFor each case, print the number of the most days that Edward can be excited for. Sample Input2 1 5 2 1 3 3 7 3 1 5 2 5 13 13 Sample Output7 18 HintFor the first case, the only Kpop festival lasts from Day 1 to Day 3. Edward can attend a party in Day 1 and a party in Day 3, he would be very excited from Day 1 to Day 7. Edward can be excited for 7 days at most. For the second case, there are 3 Kpop festivals. Edward can take part in the Kpop parties in Day 1, Day 5 and Day 13. He would be very excited from Day 1 to Day 11 and from Day 13 to Day 19. Edward can be excited for 18 days at most. Author: ZHOU, Yuchen Source: The 13th Zhejiang Provincial Collegiate Programming Contest 