102256: [AtCoder]ABC225 G - X

Problem Statement

We have a grid with $H$ horizontal rows and $W$ vertical columns. Each square contains an integer. The square $(i, j)$ at the $i$-th row from the top and $j$-th column from the left contains the integer $A_{i,j}$.

Takahashi will choose zero or more from the $H \times W$ squares and draw an X on each of them. An X is composed of a segment connecting the top-left and bottom-right corners, and a segment connecting the top-right and bottom-left corners.

Let us define Takahashi's score as $($the sum of integers contained in the squares on which X is drawn$) - C \times ($the minimum number of segments needed to draw the X's$)$.

Here, Takahashi can draw X's on diagonally adjacent squares at once.

For example, he can draw X's on the squares $(1, 1)$ and $(2, 2)$ with three segments:

• a segment connecting the top-left corner of $(1, 1)$ and the bottom-right corner of $(2, 2)$,
• a segment connecting the top-right corner of $(1, 1)$ and the bottom-left corner of $(1, 1)$,
• a segment connecting the top-right corner of $(2, 2)$ and the bottom-left corner of $(2, 2)$.

Find Takahashi's maximum possible score. Note that nothing should be drawn on unchosen squares.

Constraints

• $1 \leq H,W \leq 100$
• $1 \leq C \leq 10^9$
• $1 \leq A_{i,j} \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print Takahashi's maximum possible score.

Sample Input 1

2 2 2
2 10
8 3

Sample Output 1

12

If he chooses the squares $(1,2)$ and $(2,1)$, he can draw X's on them with three segments:

• a segment connecting the top-left corner of $(1, 2)$ and the bottom-right corner of $(1, 2)$,
• a segment connecting the top-left corner of $(2, 1)$ and the bottom-right corner of $(2, 1)$,
• a segment connecting the top-right corner of $(1, 2)$ and the bottom-left corner of $(2, 1)$.

Thus, Takahashi's score here will be $10+8-2 \times 3=12$.

There is no way to mark squares that achieves a strictly higher score, so the answer is $12$.

Sample Input 2

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

Sample Output 2

0

It is best to mark no squares.

Sample Input 3

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

Sample Output 3

9785518299

问题描述

我们有一个网格，包含$H$行和$W$列。每个格子都包含一个整数。位于第$i$行（从上数起）和第$j$列（从左数起）的格子包含整数$A_{i,j}$。

高桥将从这$H \times W$个格子中选择零个或多个，并在每个选中的格子上画一个X。一个X由一条连接左上角和右下角的线段和一条连接右上角和左下角的线段组成。

我们将高桥的得分定义为“画有X的格子中的整数之和”减去“画出所有X所需的最少线段数”的$C$倍。

在这里，高桥可以一次在对角相邻的格子上画X。

例如，他可以在格子$(1, 1)$和$(2, 2)$上画X，只需要三条线段：

• 一条连接$(1, 1)$的左上角和$(2, 2)$的右下角的线段
• 一条连接$(1, 1)$的右上角和$(1, 1)$的左下角的线段
• 一条连接$(2, 2)$的右上角和$(2, 2)$的左下角的线段

找到高桥可能得到的最大得分。 注意，未选中的格子上不应画任何东西。

约束条件

• $1 \leq H,W \leq 100$
• $1 \leq C \leq 10^9$
• $1 \leq A_{i,j} \leq 10^9$
• 输入中的所有值都是整数。

输入

从标准输入获取以下格式的输入：

$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

2 2 2
2 10
8 3

样例输出1

12

如果他选择格子$(1,2)$和$(2,1)$，他可以在它们上画X，只需要三条线段：

• 一条连接$(1, 2)$的左上角和$(1, 2)$的右下角的线段
• 一条连接$(2, 1)$的左上角和$(2, 1)$的右下角的线段
• 一条连接$(1, 2)$的右上角和$(2, 1)$的左下角的线段

因此，高桥在这里的得分为$10+8-2 \times 3=12$。

没有其他方法可以标记格子以获得更高的得分，所以答案是$12$。

样例输入2

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

样例输出2

0

最好不标记任何格子。

样例输入3

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

样例输出3

9785518299