题目描述

縦 $H$ 行、横 $W$ 列のグリッドがあります。各マスには整数が書かれており、上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ には $A_{i,j}$ が書かれています。

これから高橋くんが、$H\ \times\ W$ 個あるマスから $0$ 個以上を選び、バツ印を付けます。$1$ つのバツ印は、書かれるマスの左上の角と右下の角を結ぶ線分、および右上の角と左下の角を結ぶ線分の $2$ 本からなります。

高橋くんのスコアを、$($バツ印を付けられたマスに書かれた整数の総和$)-\ C\ \times\ ($バツ印を書くために必要な線分の本数の最小値$)$ と定義しましょう。

ここで、高橋くんは斜めに隣接するマスのバツ印を続けて書くことができます。

例えば、マス $(1,1)$ とマス $(2,2)$ にバツ印を付けるとき、高橋くんは

• マス $(1,1)$ の左上の角とマス $(2,2)$ の右下の角を結ぶ $1$ 本の線分
• マス $(1,1)$ の右上の角とマス $(1,1)$ の左下の角を結ぶ $1$ 本の線分
• マス $(2,2)$ の右上の角とマス $(2,2)$ の左下の角を結ぶ $1$ 本の線分

の計 $3$ 本によってバツ印を書くことができます。

高橋くんのスコアの最大値を求めてください。なお、バツ印を付けないマスには何も書いてはいけないことに注意してください。

输入格式

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

$H$ $W$ $C$ $A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,W}$ $A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,W}$ $\hspace{1.5cm}\vdots$ $A_{H,1}$ $A_{H,2}$ $\ldots$ $A_{H,W}$

输出格式

高橋くんのスコアの最大値を出力せよ。

题目大意

给定一个矩阵，你可以选定一些格子，得到这些格子的权值，但是你需要在这些格子中画 X，即连接两条对角线，但是对于格子 $(i,j)$ 和 $(i+1,j+1)$，倘若均需画线，你可以从 $(i,j)$ 的左上角直接画到 $(i+1,j+1)$ 的右下角，这算做一次画线，你的得分即为选定格子的权值和减去画线次数乘画线代价。

2 2 2
2 10
8 3

12

3 3 100
1 1 1
1 1 1
1 1 1

0

8 9 970861213
1313462 943495812 203775264 839015475 115668311 14701110 819458175 827176922 236492592
843915104 786367010 344840288 618248834 824858165 549189141 120648070 805825275 933750119
709330492 38579914 890555497 75314343 238373458 854061807 637519536 53226153 627677130
671706386 380984116 221773266 787763728 639374738 298691145 359138139 183373508 524415106
716502263 150803008 390520954 913021901 553285119 876389099 952721235 46809105 635239775
355621458 511843148 117663063 37274476 891025941 832254337 346436418 783134705 488516288
383723241 322408013 948364423 409068145 120813872 697127655 968230339 988041557 222591780
712959990 233114128 210373172 798667159 568746366 579461421 923556823 777007925 422249456

9785518299

提示

制約

• $1\ \leq\ H,W\ \leq\ 100$
• $1\ \leq\ C\ \leq\ 10^9$
• $1\ \leq\ A_{i,j}\ \leq\ 10^9$
• 入力はすべて整数

Sample Explanation 1

マス $(1,2)$ とマス $(2,1)$ にバツ印を付ける場合、高橋くんは - マス $(1,2)$ の左上の角とマス $(1,2)$ の右下の角を結ぶ $1$ 本の線分 - マス $(2,1)$ の左上の角とマス $(2,1)$ の右下の角を結ぶ $1$ 本の線分 - マス $(1,2)$ の右上の角とマス $(2,1)$ の左下の角を結ぶ $1$ 本の線分 の計 $3$ 本によってバツ印を書くことができます。故にこの場合の高橋くんのスコアは $10+8-2\ \times\ 3=12$ です。 これよりも真にスコアが大きくなるバツ印の付け方は存在しないため、答えは $12$ となります。

Sample Explanation 2

どのマスにもバツ印を付けないのが最善です。