#4254. Aerial Tramway

题目描述

You own a park located on a mountain, which can be described as a sequence of n points (xi, yi) from left to right, where xi,yi>0, xi<xi+1, yi!=yi+1 (that means there will not be horizontal segments in the mountain skyline), illustrated below(the numbers are the corresponding x-coordinate):


You own a park located on a mountain, which can be described as a sequence of n points (xi, yi) from left to right, where xi,yi>0, xi<xi+1, yi!=yi+1 (that means there will not be horizontal segments in the mountain skyline), illustrated below(the numbers are the corresponding x-coordinate): Since the mountain is very sloppy, some aerial tramways across the park would be very helpful. In the figure above, people can go from p4 to p9 directly, by taking a tram. Otherwise he must follow a rather

zigzag path: p4-p5-p6-p7-p8-p9.

Your job is to design an aerial tramway system. There should be exactly m trams, each following a horizontal segment in the air, between two points pi and pj. "Horizontal" means yi=yj, "in the air" means all the points in between are strictly below, i.e. yk<yi for every i<k<j. For example, no tram can travel between p2 and p9, because p4 is not strictly below p2-p9. However, you can have two trams, one

from p2 to p4, and one p4 to p9. There is another important restriction: no point can be strictly below k or more tramways, because it'll be dangerous. For example, if k=3, we cannot build these 3 tramways simultaneously: p1-p14, p4-p9, p6-p8, because p7 would be dangerous. You want to make this system as useful as possible, so you would like to maximize the total length of all tramways. For example, if m=3, k=3, the best design for the figure above is p1-p14, p2-p4 and p4-p9,the total length is 20. If m=3, k=2, you have to replace p1-p14 with p11-p13, the total length becomes 9.

输入格式

There will be at most 200 test cases. Each case begins with three integers n, m and k(1<=n,m<=200, 2<=k<=10), the number of points, the number of trams in your design and the dangerous parameter introduced earlier. The next line contains n pairs of positive integers xi and yi.(1<=xi,yi<=10^5).

输出格式

For each test case, print the case number and the maximal sum. If it is impossible to have exactly m tramways, print -1.

样例

样例输入

14 3 3   

1 8   

2 6   

3 4   

4 6   

5 3   

6 4   

7 1   

8 4   

9 6   

10 4   

11 6   

12 5   

13 6   

14 8   

14 3 2   

1 8   

2 6   

3 4   

4 6   

5 3   

6 4   

7 1   

8 4   

9 6   

10 4   

11 6   

12 5   

13 6   

14 8 

样例输出

Case 1: 20   

Case 2: 9 

数据范围与提示

2015年湖南省大学生程序设计竞赛