AT_abc225_g [ABC225G] X

有一个高为 $H$ 行、宽为 $W$ 列的网格。每个格子里写有一个整数，对于从上往下第 $i$ 行、从左往右第 $j$ 列的格子 $(i,j)$，写有 $A_{i,j}$。 现在高桥君可以从 $H \times W$ 个格子中选择 $0$ 个或多个格子，在这些格子上画上“叉号”。每个“叉号”由两条线段组成，分别连接该格子的左上角与右下角，以及右上角与左下角。 高桥君的得分定义为：（被画上“叉号”的格子中所写整数的总和）减去 $C$ 乘以（画出这些“叉号”所需线段的最小数量）。 这里，高桥君可以将斜向相邻的格子的“叉号”连续画在一起。 例如，当在格子 $(1,1)$ 和格子 $(2,2)$ 上画“叉号”时，高桥君可以用以下 $3$ 条线段完成： - 一条连接格子 $(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}$ > $\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$ - 输入均为整数 ### 样例解释 1 如果在格子 $(1,2)$ 和格子 $(2,1)$ 上画“叉号”，高桥君可以用以下 $3$ 条线段完成： - 一条连接格子 $(1,2)$ 的左上角和格子 $(1,2)$ 的右下角的线段 - 一条连接格子 $(2,1)$ 的左上角和格子 $(2,1)$ 的右下角的线段 - 一条连接格子 $(1,2)$ 的右上角和格子 $(2,1)$ 的左下角的线段 因此，这种情况下的得分为 $10+8-2\times 3=12$。不存在比这更高的得分方案，所以答案为 $12$。 ### 样例解释 2 不在任何格子上画“叉号”是最优的。 由 ChatGPT 4.1 翻译