应急架桥

一场暴雨冲毁了山区中的部分道路。救援队需要从地图左上角的营地 $(1,1)$ 前往右下角的安置点 $(n,m)$。

地图是一个 $n$ 行 $m$ 列的网格。每个格子中的数为：

• $-1$：这个格子是断路，不能停留；
• 非负整数：这个格子可以到达，数值表示救援队到达该格子时取得的补给数量。

救援队每次可以从当前格子向右或向下移动一格，且到达的格子不能是断路。

此外，救援队至多可以架桥 $k$ 次。每次架桥可以向右或向下跨过恰好一个格子，直接到达同一方向上距离为 $2$ 的格子。被跨过的格子可以是断路，也可以是普通格子；救援队不会取得被跨过格子的补给。架桥后的落脚格必须在地图内，并且不能是断路。

救援队会取得每个实际到达格子的补给，包括起点和终点。请计算从 $(1,1)$ 到达 $(n,m)$ 最多可以取得多少补给。若无法到达，输出 $-1$。

输入格式

第一行输入三个整数 $n,m,k$，分别表示地图的行数、列数和最多架桥次数。

接下来 $n$ 行，每行输入 $m$ 个整数，描述地图。每个整数为 $-1$ 或一个非负整数。

输出格式

输出一个整数，表示最多可以取得的补给数量；若无法到达，输出 $-1$。

样例 1

输入

3 4 2
1 2 -1 10
2 -1 5 2
1 3 4 8

输出

23

说明

可以依次到达 $(1,1)$、$(1,2)$，架桥跨过 $(1,3)$ 到达 $(1,4)$，再向下到达 $(2,4)$ 和 $(3,4)$。总补给为 $1+2+10+2+8=23$。

样例 2

输入

1 5 2
5 4 3 2 1

输出

15

说明

虽然最多可以架桥两次，但本例不架桥能够取得更多补给。注意，架桥次数可以少于 $k$。

更多样例

样例 3、样例 4 和样例 5 请分别查看附件中的 Data/sample3.in、Data/sample3.ans，Data/sample4.in、Data/sample4.ans 与 Data/sample5.in、Data/sample5.ans。

【数据规模与约定】

对于所有测试数据：

• $1\le n,m\le 1000$；
• $nm\le 10^5$；
• $0\le k\le 10$；
• 每个格子为 $-1$ 或 $0$ 到 $10^9$ 之间的整数。

各子任务的额外限制如下。没有额外限制的子任务仍满足上述完整数据范围。

点击下载本题选手目录