积木游戏

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file bricka.in Output file bricka.out

【题目描述】


积木游戏是一种创造建筑物的游戏,像所有的玩具积木游戏一样,它也是使用一组积木来搭建建筑物。

在这个问题中,考虑一个用一组积木搭建的长方形建筑,我们的任务是从建筑中移走K块积木,使得剩余的积木保持稳定,剩余的积木需满足下面要求:

(1)剩余建筑中的每一层都由一些在行中连续的积木所组成;

(2)每一层都至少要有一块积木有下层积木的支撑;

(3)在最底层要保留至少一块积木。

每块积木都有一个目测值(为一个非负整数刻在其表面上),我们希望剩余积木的目测值总和最大,你能告诉我们这个和是多少吗?

举例说明,下面为输入样例所对应的图示,右边为按照上述规则所得到的最优解,请注意,因为没有规定有多少层必须保留,所以我们可以丢弃最上面的一些层。


 原始建筑                                                         最优解



【输入格式】


输入文件第一行有一个正整数T(T<=20),表示接下来测试数据的个数。

每个测试数据的第一行有三个整数:N,M,K,(0<N,M<=64;max(NM-64,0)<=K<NM)。

接下来有N行,每行有M个整数,为每个积木的目测值,第一行表示建筑的最上层,最后一行为建筑的最底层。所有的目测值均为小于32768的非负整数。

所有数都由空格隔开。


【输出格式】


对于每个测试数据,输出只有一行,形如“Case X:Y”(不包括双引号),其中X表示测试数据的编号(从1开始),Y表示最大总和。


【样例输入】

1
6 4 12
1 1 1 1
1 7 14 1
9 4 18 18 
2 4 5 5
1 7 1 11
3 2 7 16

【样例输出】

Case 1:118

【提示】

在此键入。

【来源】

在此键入。