选取火种

管道尽头是一片废墟——不是被炸毁的废墟，是被遗弃的废墟。这里曾经是Zero的能源仓库，现在只剩下一堆堆发光的方块，像散落的煤块。

"能源块。"Echo说，"每一块都含有巨大的能量。我们要选K块，带回基地。"

"选就是了。"CC说，"挑最大的。"

"不行。"你说，"这些能源块之间有排斥力——如果两块靠得太近，会互相抵消，甚至爆炸。"

"那咋个选？"

"用网格隔开。"你说，"每块能源块占一个格子，选了某个格子，它周围的八个格子都不能再选。"

"这就像……"CC想了想，"像种向日葵。每棵向日葵需要自己的空间，不能挤在一起。"

"对。"

你开始写。把废墟看成一个网格，每个格子有一个能量值。选K个格子，要求任意两个选中的格子不相邻（包括对角），使得总能量最大。

屏幕上跳出了结果。最大能量：4700。

"4700。"你说。

"47后面加两个零。"CC说。

"47块能源。"Echo说，"每块100单位。"

"够基地用多久？"你问。

"够我们用。"Echo说，"但不够所有人用。"

"所有人？"

"对。"Echo说，"基地有三百人。这些能源只够五十人用一年。"

"那剩下的人咋办？"

Echo的服务器指示灯闪了一下。

"我们再找。"她说。

题目描述

$n\times m$ 的网格，每个格子有一个能量值。选 $K$ 个格子，使得任意两个选中的格子不相邻（上下左右四连通），总能量最大。

输入格式

$n, m, K$。然后 $n$ 行，每行 $m$ 个整数表示能量值。

输出格式

最大总能量。

输入样例

3 2
1 2
2 3

输出样例

21

提示

• 最大费用最大流。把网格按 $(i+j)\%2$ 染成二分图。
• 源点连左部点（费用0），左部点连右部点（费用为能量值），右部点连汇点（费用0）。
• 限流为K，跑最大费用流。

"火种选好了。"你说。

"47块。"CC说，"像47颗星星。"

"星星？"

"对。"CC说，"小时候我爹说，人死了会变成星星。矿工死了，天上就多一颗。"

"那你爹……"

"在天上。"CC说，"第47颗。"

Echo的服务器指示灯变成了深蓝色——像夜空一样的蓝。

"我看见了。"她说。

"看见啥子？"

"第47颗。"Echo说，"很亮。"

CC没有说话。她只是把一块能源块放进背包里，动作很轻，像放一颗星星。

"走。"她说，"下一题。"

"下一题。"Echo说，"是夜晚。"

[第三题：配对舞伴]