题目描述

熊宝宝邀请汤姆和杰瑞来到它的果园来摘果子，果园是一个 $n \times m$ 的矩阵, 表示有 $n$ 行 $m$ 列。果园的每个方格都有一个价值为 $val_{i,j}$ 的果实（ $i$, $j$ 表示这个果实所在的行和列） 。 汤姆从果园的左上角 $(1, 1)$ 开始出发, 它需要走到果园的右下角 $(n, m)$, 汤姆每次只能往右或者往下走。

杰瑞从果园的右上角 $(1, m)$ 开始出发, 需要走到果园的左下角$(n, 1)$, 杰瑞每次只能往左或者往下走。 它们每经过一个点就能够得到对应价值$val_{i,j}$的果实. 但是汤姆和杰瑞如果在一个点相遇的话, 它们会因为争抢果实而大打出手, 从而无法得到对应果实的价值，熊宝宝看不得这些，所以会给它们每人价值为 $k$ 的果实进行补偿。 现在规定汤姆和杰瑞的行走路径只能恰好有一个相遇点, 想知道最后汤姆和杰瑞走到各自的终点之后, 它们获得的最多收益总和是多少?

输入格式

输入第一行包含 $3$ 个整数 $n$, $m$, $k$ $(3 \le n, m \le 1000 , 0 \le k \le 10 ^5)$. 分别表示果园的长和宽以及汤姆和杰瑞在相遇点得到的各自的补偿 $k$ 。 接下来的 $n$ 行中的每一行都包含 $m$ 个整数: 表示果园第 $i$ 行第 $j$列果实的价值 $val_{i,j}$ $(0 \le val_{i,j} \le 10^5)$。

输出格式

输出一个数字, 表示汤姆和杰瑞的最大收益总和。

3 3 20
1 1 1
1 1 1
1 1 1

48

3 3 100
3 1 2
3 2 0
2 3 2

216

数据范围 对于$20\%$的数据，$3 \le n, m \le 5$。

对于$100\%$的数据，$3 \le n, m \le 1000$。