#P4254. Aerial Tramway

    ID: 3472 传统题 1000ms 128MiB 尝试: 51 已通过: 24 难度: 7 上传者: 标签>CF2200提高树上背包子树合并剪除无效容量鸣谢刘汝佳先生授权使用

Aerial Tramway

题目描述

一条山脊由从左到右的 nn 个点 pi=(xi,yi)p_i=(x_i,y_i) 描述。横坐标严格递增,相邻两点的高度不同。

要修建恰好 mm 条索道。每条索道连接两个山脊点 pi,pjp_i,p_j(i<ji<j),并且必须满足 yi=yjy_i=y_j,以及每个满足 i<r<ji<r<j 的山脊点都满足 yr<yiy_r<y_i。这条索道的长度为 xj−xix_j-x_i。任何一个山脊点都不能同时严格位于 kk 条或更多索道的下方。索道的端点本身不计入这条索道下方的点。

求所建索道长度之和的最大值。

输入格式

输入包含至多 200200 组数据,读至文件末尾。每组的第一行是 n,m,kn,m,k,接下来给出 nn 对整数 xi,yix_i,y_i。

1≤n,m≤2001\le n,m\le200,2≤k≤102\le k\le10,1≤xi,yi≤1051\le x_i,y_i\le10^5。

输出格式

对第 cc 组数据,输出一行,格式为 Case c: answer。如果无法修建恰好 mm 条索道,令 answer=−1\mathrm{answer}=-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

UVa 12929 原题及示意图