G - X

得分：$600$ 分

问题描述

有一个 $H$ 行 $W$ 列的方格网格。每个格子内包含一个整数。第 $i$ 行第 $j$ 列的格子包含整数 $A_{i,j}$。

高濑可以选择一个或多个 $H \times W$ 的格子，并在上面画个 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}$

输出

打印高濑可能得到的最大得分。

2 2 2
2 10
8 3

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

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