题目描述

本题使用文件输入输出：输入文件名为 gem.in，输出文件名为 gem.out。

一座 $n$ 行 $m$ 列的矿洞，行从上到下编号 $1 \sim n$，列从左到右编号 $1 \sim m$。每个格子要么藏着一些宝石，价值为一个非负整数 $a_{i,j}$；要么是一个陷阱，用 $-1$ 表示。

小 Z 从左上角 $(1,1)$ 出发，每一步只能向右或向下走一格，最终要走到右下角 $(n,m)$。经过有宝石的格子就能拿走全部宝石；经过陷阱会受伤，但不会拿到任何东西。小 Z 的防护装备最多能承受 $k$ 次受伤，也就是说，整条路线上经过的陷阱不能超过 $k$ 个。

请你求出小 Z 能拿到的宝石总价值的最大值。如果不存在经过陷阱不超过 $k$ 个的路线，输出 $-1$。

保证 $(1,1)$ 和 $(n,m)$ 都不是陷阱。

输入格式

输入文件名为 gem.in。

第一行三个整数 $n, m, k$。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个数是 $a_{i,j}$；$a_{i,j} = -1$ 表示陷阱。

输出格式

输出文件名为 gem.out。

一行一个整数，表示能拿到的最大宝石总价值；无法到达时输出 $-1$。

样例 #1

样例输入 #1

3 3 1
1 -1 3
-1 -1 6
7 8 9

样例输出 #1

25

样例解释

从 $(1,1)$ 出发必须先经过 $(1,2)$ 或 $(2,1)$，两者都是陷阱，所以至少受伤一次。

最优路线是 $(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)$，只经过陷阱 $(2,1)$，拿到 $1+7+8+9 = 25$。

另一条路线 $(1,1) \to (1,2) \to (1,3) \to (2,3) \to (3,3)$ 也只受伤一次，但只能拿到 $1+3+6+9 = 19$。

样例 #2

样例输入 #2

3 3 0
1 -1 3
-1 -1 6
7 8 9

样例输出 #2

-1

样例解释

不允许受伤，而从 $(1,1)$ 走出去的两个格子都是陷阱，无法到达。

提示

数据范围

• 对于 $30\%$ 的数据：$n, m \le 10$；
• 对于 $60\%$ 的数据：$k = 0$；
• 对于 $100\%$ 的数据：$1 \le n, m \le 300$，$0 \le k \le 10$，$-1 \le a_{i,j} \le 1000$。