Alice と Bob は、$N$ 行 $M$ 列（$M$ は偶数）のグリッドでゲームを行います。また、正の整数 $K$ が与えられます。最初、グリッドの各セルには $0$ 以上 $K$ 以下の値が入っており、すべてのセルは「未マーク」の状態です。プレイヤーは交互に手番を行い、Alice が先攻です。現在のプレイヤーが操作を行えなくなった時点でゲームは終了します。
各プレイヤーは自分の手番で、グリッドの未マークのセルを 1 つ選び、さらに $0$ 以上 $K$ 以下の整数 $a$ を選びます。そして、選んだセルの値を $a$ に変更し、選んだセルと同じ列にあるすべてのセル（選んだセルを含む）を「マーク」します。
グリッドの「非対称度（asymmetry）」は、グリッドを中央で水平に反転させたときの、対応するセル同士の値の差の絶対値の総和です。より形式的には、以下のように定義されます。
$$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right)$$
ここで、$g_{i,j}$ は上から $i$ 行目、左から $j$ 列目のセルの値です。例えば、以下の $2 \times 4$ グリッドの非対称度は $|8-0| + |4-2| + |6-6| + |7-9| = 12$ となります。
| 8 | 4 | 2 | 0 |
|---|---|---|---|
| 6 | 7 | 9 | 6 |
Alice はゲーム終了時のグリッドの非対称度を最小化したいと考えており、Bob は最大化したいと考えています。両者が最適にプレイする場合、最終的なグリッドの非対称度はいくつになるでしょうか。
入力
入力の最初の行は、3 つのスペース区切りの整数 $N, M, K$ ($1 \le N, M \le 2000$, $M$ は偶数, $1 \le K \le 10^9$) で構成されます。
続く $N$ 行にはそれぞれ $M$ 個の整数が含まれます。$i$ 行目には、上から $i$ 行目の左から右へのセルの値 $g_{i,1}, \dots, g_{i,M}$ ($0 \le g_{i,j} \le K$) が記述されています。
以下の表は、25 点分の配点の内訳を示しています。
| 配点 | $N$ の制約 | $M$ の制約 | $K$ の制約 |
|---|---|---|---|
| 2 点 | $N = 1$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
| 3 点 | $1 \le N \le 2000$ | $M = 2$ | $K = 1$ |
| 3 点 | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10$ |
| 3 点 | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10^9$ |
| 4 点 | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $K = 1$ |
| 4 点 | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10$ |
| 6 点 | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
出力
Alice と Bob が最適にプレイした場合の、最終的なグリッドの非対称度を整数で出力してください。
入出力例
入力 1
3 2 1 1 0 1 0 0 0
出力 1
2
注記
出力 1 の解説： 列は 2 つしかないため、各プレイヤーは 1 手ずつ行います。Alice が先攻の場合、以下の操作が可能です。
- 1 列目の値が 1 であるセルのいずれかを選び、その値を 0 に変更する。その後、Bob の最適な手は、同じ行の 2 列目のセルの値を 1 にすることである。最終的なグリッドは、元のグリッドの 0 と 1 が並ぶ最初の 2 行のうち、ちょうど 1 行が入れ替わったものとなる。このようなグリッドの非対称度は $|1-0| + |0-1| + |0-0| = 2$ である。
- 2 列目の最初の 2 行にあるセルのいずれかを選び、その値を 1 に変更する。その後、Bob の最適な手は、同じ行の 1 列目のセルの値を 0 にすることである。同様に、最終的なグリッドは元のグリッドの 0 と 1 が並ぶ最初の 2 行のうち、ちょうど 1 行が入れ替わったものとなる。このようなグリッドの非対称度は 2 である。
- 3 行目のセルのいずれかを選び、その値を 1 に変更する。その後、Bob の最適な手は、3 行目のもう一方のセルの値を 0 にすることである。選んだセルはすでに値 0 を持っていたことに注意。このような操作は許可される。最終的なグリッドは各行に 0 と 1 を持つことになり、非対称度は 3 となる。
- 任意のセルを選び、その値を現在の値のままにする。その後、Bob の最適な手は、残っている未マークの列の 3 行目のセルの値を 1 にすることである。最終的なグリッドは各行に 0 と 1 を持つことになり、非対称度は 3 となる。
Alice がどのように動いても、Bob は非対称度が少なくとも 2 になるようにプレイできることがわかる。Alice が最初の手を最適に選べば、Bob が最終的な非対称度を 2 より大きくできないようにすることができる。したがって、両者が最適にプレイした場合の非対称度は 2 である。
入力 2
1 10 21 4 2 0 6 7 6 9 9 10 21
出力 2
55
注記
出力 2 の解説： 行は 1 つしかないため、各プレイヤーは未マークのセルを選び、0 以上 21 以下の任意の値を設定する。各プレイヤーが 5 手ずつ行った後、すべての 10 セルがマークされてゲームは終了する。
入力 3
4 6 986754321 219759391 882760615 762656191 423465948 621463211 136889371 215621504 385106915 740086459 417915224 551800597 572994766 176308756 365311996 635683450 907755406 590000050 586083433 607011121 457147795 837558908 684766852 946836347 303039615
出力 3
3972378656
注記
出力 3 の解説： 答えは 32 ビット整数に収まらない可能性があることに注意すること。