矩阵分割

题目描述

给定一个 $H$ 行 $W$ 列的资源矩阵，矩阵位置 $(i,j)$ 拥有资源量 $s_{i,j}$。

你需要进行 $T$ 次分割操作，最终将整块矩阵分割为 $T+1$ 个子矩阵。

每次分割只能选择以下两种合法操作之一：

1. 横向分割：选取一个行数 $\ge 2$ 的子矩阵，在其任意相邻两行之间切开，分成两个新子矩阵。
2. 纵向分割：选取一个列数 $\ge 2$ 的子矩阵，在其任意相邻两列之间切开，分成两个新子矩阵。

分割完成后，得到 $T+1$ 块子矩阵，设每块的资源总和为 $x_1,x_2,\dots,x_{T+1}$。 记 $M$ 为资源总和的最大值，$m$ 为资源总和的最小值。

求 $M-m$ 的最小可能值。

输入格式

H W T
s11 s12 … s1W
s21 s22 … s2W
……
sH1 sH2 … sHW

输出格式

输出分割后最大资源和与最小资源和的最小差值。

输入输出样例 #1

输入 #1

2 3 4
2 3 4
4 1 3

输出 #1

2

输入输出样例 #2

输入 #2

2 2 3
0 0
0 0

输出 #2

0

说明/提示

约束条件

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

样例解释 1

经过最优分割后，各块资源量分别为 $2,4,4,4,3$。 最大值为 $4$，最小值为 $2$，差值为 $2$，为理论最小值。