当前没有测试数据。

G - 草莓战争

得分：600分

问题描述

我们有一块矩形蛋糕，它被分割成$H$行和$W$列的小块，第$i$行第$j$列的小块上有$s_{i,j}$个草莓。

你将进行$T$次切割，将蛋糕分成$T+1$个部分。每次切割可以按照以下两种方式之一进行。

• 选择一个有两行或两列以上小块的部分，然后选择两行或两列相邻的小块，沿着它们的边界将该部分切割成两个更小的部分。
• 选择一个有两行或两列以上小块的部分，然后选择两行或两列相邻的小块，沿着它们的边界将该部分切割成两个更小的部分。

你希望将草莓尽可能均匀地分配在这些部分中。
设$M$和$m$分别为这些$T+1$个部分中的最大和最小草莓数目。求$M－m$的最小值。

约束

• $1 \leq H,W \leq 6$
• $1 \leq T \leq HW-1$
• $0 \leq s_{i,j} \leq 10^{16}$
• 输入中的所有值均为整数。

输入

从标准输入中以以下格式给出：

$H$ $W$ $T$

$s_{1,1}$ $\ldots$ $s_{1,W}$

$\vdots$

$s_{H,1}$ $\ldots$ $s_{H,W}$

输出

输出答案。

2 3 4
2 3 4
4 1 3

2

下图展示了一种切割蛋糕的方式，使得左上、左下、中间、右上和右下部分的草莓数目分别为$2$、$4$、$4$、$4$和$3$。在这种情况下，最大和最小草莓数目之间的差距为$4-2=2$。不可能找到更小的差距，因此答案是2。

2 2 3
0 0
0 0

0