测试数据来自 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