草莓之战

题目描述

我们有一块长方形蛋糕,被分成 $H$ 行 $W$ 列的小块。从上数第 $i$ 行、从左数第 $j$ 列的小块上有 $s_{i,j}$ 颗草莓。

你将切 $T$ 刀,把蛋糕分成 $T+1$ 块。每一刀按以下两种方式之一进行:

• 选择一块包含两行或更多行小块的现有蛋糕块,再选择其中相邻的两行,沿它们的边界切开,分成两块较小的蛋糕块。
• 选择一块包含两列或更多列小块的现有蛋糕块,再选择其中相邻的两列,沿它们的边界切开,分成两块较小的蛋糕块。

你想让草莓尽可能均匀地分配到切出的各块蛋糕上。

设 $x_1,x_2,\ldots,x_{T+1}$ 为切出的 $T+1$ 块蛋糕上的草莓数,$M$ 和 $m$ 分别为其中的最大值和最小值。求 $M-m$ 的最小可能值。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

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