Strawberry War

时间限制：4 秒 / 内存限制：1024 MB

Description

我们有一个长方形的蛋糕。它被分割成 $H$ 行和 $W$ 列的小块，位于从上往下第 $i$ 行、从左往右第 $j$ 列的小块上有 $s_{i,j}$ 颗草莓。

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

1. 选择一个现有的包含两行或更多行的块，再从中选择两行相邻的行，沿着它们之间的边界切割，将其分成两个较小的块。
2. 选择一个现有的包含两列或更多列的块，再从中选择两列相邻的列，沿着它们之间的边界切割，将其分成两个较小的块。

你希望将草莓尽可能均匀地分配到最终的块中。
设 $x_1, x_2, \dots, x_{T+1}$ 为最终 $T+1$ 块中草莓的数量，$M$ 和 $m$ 分别为这些数量中的最大值和最小值。求 $M - m$ 的最小可能值。

Input

• 第一行包含三个整数 $H$、$W$ 和 $T$，分别表示蛋糕的行数、列数以及切割次数。
  $1 \leq H, W \leq 6$，$1 \leq T \leq HW - 1$
• 接下来有 $H$ 行，每行包含 $W$ 个整数，表示每个小块上的草莓数量。
  $0 \leq s_{i,j} \leq 10^{16}$
• 输入中的所有值均为整数。

Output

输出 $M - m$ 的最小可能值。

Example

Sample Input 1

2 3 4
2 3 4
4 1 3

Sample Output 1

2

解释

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

Sample Input 2

2 2 3
0 0
0 0

Sample Output 2

0