AT_abc225_g [ABC225G] X

[problemUrl]: https://atcoder.jp/contests/abc225/tasks/abc225_g 縦 $ 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} $

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

### 制約 - $ 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 どのマスにもバツ印を付けないのが最善です。