T463908 修桥

A 市可以看成一个 $H \times W$ 的网格，现在令 $(i,j)$ 为第 $i$ 行第 $j$ 列的格子。 在这之前，人们的出行一般只通过网格图上原有的边来行走，但这时候有人想到如果修起从一个格子到另一个格子的直通隧道，那么人们的出行将会方便许多。 因此他向政府申请修建一个这样的直通隧道。但政府不想花费太多的钱，因此只希望修一条隧道，且想知道最少需要花多少钱来修建这一条隧道。 隧道的修建的步骤如下：首先选择两个不同的格子 $(i,j),(i',j')$，然后分别花费 $A_{i,j},A_{i',j'}$ 的钱来挖洞，然后就需要在地底挖隧道，这时候的需要的钱是 $C \times (|i-i'|+|j-j'|)$。因此，修建一条隧道的总花费是 $A_{i,j} + A_{i', j'} + C\times (|i-i'|+|j-j'|)$。

无

无

**【样例解释】** 选择 $(1,1)$ 与 $(2,3)$ 之间挖隧道，那么花费就是 $1 + 3 + 2 \times 3 = 10$。 --- **【数据范围】** 对于 40\% 的数据，$4 \le H \times W \le 1000$。 对于 100\% 的数据，$2 \le H,W \le 1000$，$1\le C, A_{i,j} \le 10^9$。