题目描述

我们有一个矩形蛋糕，被分成 $H$ 行 $W$ 列的部分，第 $i$ 行从上往下数，第 $j$ 列从左往右数的部分上有 $s_{i,j}$ 个草莓。

你将进行 $T$ 次切割，将蛋糕切成 $T+1$ 块。每次切割可以采用以下两种方式之一：

• 选择一个已存在的部分，该部分拥有两行或两列以上的部分。此外，选择该部分中的两行或两列相邻的部分，然后沿着它们之间的边界将该部分切割为两个较小的部分。
• 选择一个已存在的部分，该部分拥有两列或两行以上的部分。此外，选择该部分中的两列或两行相邻的部分，然后沿着它们之间的边界将该部分切割为两个较小的部分。

你希望尽可能均匀地分布草莓到切割后的部分中。
设 $x_1,x_2,\\ldots,x_{T+1}$ 为切割后的 $T+1$ 个部分上的草莓数量，$M$ 和 $m$ 分别为其中的最大值和最小值。求 $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}$

输出

输出答案。

示例输入 1

2 3 4
2 3 4
4 1 3

示例输出 1

2

下图展示了一种切割蛋糕的方式，使得左上、左下、中间、右上和右下五块蛋糕上分别有 $2$、$4$、$4$、$4$ 和 $3$ 个草莓。在这里，草莓数量的最大值和最小值之差为 $4-2=2$。无法得到更小的差值，因此答案为 $2$。

示例输入 2

2 2 3
0 0
0 0

示例输出 2

0