#P4254. Aerial Tramway
Aerial Tramway
题目描述
一条山脊由从左到右的 个点 描述。横坐标严格递增,相邻两点的高度不同。
要修建恰好 条索道。每条索道连接两个山脊点 (),并且必须满足 ,以及每个满足 的山脊点都满足 。这条索道的长度为 。任何一个山脊点都不能同时严格位于 条或更多索道的下方。索道的端点本身不计入这条索道下方的点。
求所建索道长度之和的最大值。
输入格式
输入包含至多 组数据,读至文件末尾。每组的第一行是 ,接下来给出 对整数 。
,,。
输出格式
对第 组数据,输出一行,格式为 Case c: answer。如果无法修建恰好 条索道,令 。
样例
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