该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

熊宝宝邀请汤姆和杰瑞来到它的果园来摘果子，果园是一个 $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)$

输出格式

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

输入样例1：

3 3 20
10 100 35
100 1 100 
15 100 20

输出样例1：

520

数据范围

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

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