画 X

题目描述

我们有一个 $H$ 行 $W$ 列的网格,每个格子里写着一个整数。从上数第 $i$ 行、从左数第 $j$ 列的格子 $(i, j)$ 中写着整数 $A_{i,j}$。

高桥君将从 $H \times W$ 个格子中选择任意多个(也可以一个都不选),在每个选中的格子上画一个 X。X 由连接左上角与右下角的线段,以及连接右上角与左下角的线段组成。

定义高桥君的得分为(画有 X 的格子中的整数之和) $- C \times$(画这些 X 所需的最少线段数)。

这里,高桥君可以在对角线方向相邻的格子上一次性画出 X。

例如,他可以用 3 条线段在格子 $(1, 1)$ 和 $(2, 2)$ 上画出 X:

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

求高桥君的最大可能得分。注意,未被选中的格子上不能画任何东西。

输入格式

输入按以下格式从标准输入给出:

$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)$,可以用 3 条线段在它们上面画出 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

数据范围

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