简单的网络游戏
测试数据来自 system/1239
描述
在某款极具技术含量的网络游戏中,佳佳靠着他的聪明智慧垄断了游戏中的油田系统。
油田里有许多油井,这些油井排成一个M*N的矩形。每个油井都有一个固定的采油量。每两个相邻的油井之间有一条公路,这些公路是油井与油井之间唯一的运油方式。佳佳的领地在油田的右方和下方,他需要把采到的油通过这些公路运输到他的领地。为了保证采到的油以最快的方式供给右方和下方的领地,对于每个油井,佳佳总是将采到的油分成非空的两部分,将其中一部分沿公路一直向右运输到油田的右边界,将另一部分沿公路一直向下运输到油田的下边界。
然而树大招风,网络游戏中的GM以保证游戏公平为由,要求佳佳主动贡献出K个油井。更惨的是,失去某些油井不单意味着采油量减少,这还将会导致运输线路的中断。如果佳佳贡献出了某个油井,那么所有要经过这个油井的运输任务将无法完成。
佳佳想保证贡献K个油井之后自己的损失最小(损失即为失去的所有油井的采油量之和),而他希望其他的所有油井还能够像往常一样正常运输。于是他向你求救,希望你能帮助他实现他的想法。
格式
输入格式
第一行有三个用空格隔开的正整数M,N和K,它们分别表示油田的长、宽和佳佳需要贡献出的油田数。输入数据保证K<=M*N。
以下N行中每行有M个用空格隔开的正整数。这些正整数保证不超过10000,它们描述了油田中各个油井的采油量。
对于30%的数据,M<=10,N<=10;
对于100%的数据,M<=60,N<=60。
输出格式
一个整数,表示佳佳最少要损失的采油量。
样例1
样例输入1
5 3 4
3 4 1 4 5
1 10 7 8 13
3 5 8 9 11
样例输出1
9
限制
各测试点1秒
提示
样例说明:
佳佳贡献出下面标有“x”的油井是符合条件的最小损失方案。
x x x 4 5
x 10 7 8 13
3 5 8 9 11
来源
OIBH命题组原创 By matrix67