题目描述

長方形のケーキがあります。このケーキは $H$ 行 $W$ 列に並ぶ区画に分かれていて、上から $i$ 行目、左から $j$ 列目の区画にはイチゴが $s_{i,j}$ 個載っています。

あなたは $T$ 回の切断を行ってケーキを $T+1$ 切れに分割することにしました。各回の切断は、次のいずれかの方法で行います。

• 現存するケーキであって、区画の行の数が $2$ 以上であるものを選ぶ。さらに、そのケーキから隣接する $2$ 行を選び、その境界でケーキを切断してより小さなケーキ $2$ 切れに分割する。
• 現存するケーキであって、区画の列の数が $2$ 以上であるものを選ぶ。さらに、そのケーキから隣接する $2$ 列を選び、その境界でケーキを切断してより小さなケーキ $2$ 切れに分割する。

あなたの目標は、分割後のケーキに載ったイチゴの数をできるだけ均等にすることです。
分割後の $T+1$ 切れのケーキに載ったイチゴの個数を $x_1,x_2,\ldots,x_{T+1}$ として、そのうち最大のものを $M$、最小のものを $m$ とするとき、$M－m$ がとりうる最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给定一个 $H\times W$ 的矩阵，对于每一部分，我们可以挑选相邻的行或列中间切一道，变成两个部分。将这个矩阵分成 $T+1$ 个部分，对于每个部分，权值为部分内元素的和。要求最小化最大值减最小值的差。

translated by 月。

2 3 4
2 3 4
4 1 3

2

2 2 3
0 0
0 0

0

提示

制約

• $1\ \leq\ H,W\ \leq\ 6$
• $1\ \leq\ T\ \leq\ HW-1$
• $0\ \leq\ s_{i,j}\ \leq\ 10^{16}$
• 入力はすべて整数

Sample Explanation 1

下のように切り分けると左上のケーキに $2$ 個、左下のケーキに $4$ 個、中央のケーキに $4$ 個、右上のケーキに $4$ 個、右下のケーキに $3$ 個のイチゴが載った状態になり、イチゴの個数の最大値と最小値の差は $4-2=2$ となります。差をこれよりも小さくすることは出来ないため、$2$ が答えとなります。