配点 : $600$ 点

問題文

長方形のケーキがあります。このケーキは $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$ がとりうる最小値を求めてください。

制約

• $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}$

出力

答えを出力せよ。

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