解题思路

本题使用记忆化搜索。

因为符文值最大为 $100$，并且是否能够铭刻当前符文，只与上一次铭刻的值有关。

定义搜索状态：

$dfs(x,y,rest,last)$

题目内容

地下迷宫试炼有 $n$ 行 $m$ 列格子。探险者从起点走到终点，途中可以铭刻符文得分，但体力有限。

格子取值约定：$-1$ 是墙，不能进入；$0$ 是空通道，可以通过，没有符文；$1 \sim 100$ 是带符文的通道，数值为该格符文值。每次可向上下左右四格相邻的通道移动一步，不能出界、不能穿墙。每移动一步消耗 $1$ 点体力，初始体力为 $P$，体力为 $0$ 时不能再移动。

铭刻规则：

• 人已经站在某格时，若该格符文值为正整数 $v$，可以选择铭刻或跳过。
• 铭刻必须严格递增：设上一次成功铭刻的值为 $\textit{last}$（尚未铭刻过任何符文时 $\textit{last}=0$），仅当 $v > \textit{last}$ 时才能铭刻该格，铭刻后 $\textit{last}$ 变为 $v$，得分加上 $v$。
• 同一格可以多次路过；某次路过选择跳过的，之后仍可再铭刻，但必须满足严格递增。
• 出发时人已经在起点上，可以先决定是否铭刻起点，这一步不消耗体力。

通关方式：在体力用尽之前的某一个时刻，人位于终点即可结束试炼，得分以结束那一刻已经铭刻的总和计算。可以在第一次走到终点时结束，也可以带着剩余体力继续走，稍后再回到终点结束。若在体力约束下无法到达终点，试炼失败。

请给出通关时能得到的最大得分。

输入描述

第一行三个整数 $n$、$m$、$P$。

第二行四个整数 $s_x$、$s_y$、$t_x$、$t_y$，表示起点和终点的行列坐标，下标从 $1$ 开始。

接下来 $n$ 行，每行 $m$ 个整数，给出迷宫格子的取值。

约束

$1 \le n,m \le 12$

$0 \le P \le 20$

$1 \le s_x,t_x \le n$

$1 \le s_y,t_y \le m$

格子取值仅为 $-1$ 或 $[0,100]$ 内的整数

起点、终点保证不是墙

输出描述

输出一个整数：通关的最大得分。能到达终点但未铭刻任何符文时输出 $0$；无法到达终点时输出 $-1$。

样例1

输入

3 3 4
1 1 3 3
1 10 2
-1 0 4
-1 -1 8

输出

15

说明

起点 $(1,1)$，终点 $(3,3)$，体力恰好够走最短的 $4$ 步。一条路径为 $(1,1) \to (1,2) \to (1,3) \to (2,3) \to (3,3)$，格子值 $1,10,2,4,8$。

若在 $10$ 处铭刻，之后 $2$、$4$、$8$ 都不大于 $10$，最多再带上起点的 $1$，总分为 $11$。跳过 $10$，依次铭刻 $1$、$2$、$4$、$8$，总和为 $15$。

另一条 $4$ 步路径 $(1,1) \to (1,2) \to (2,2) \to (2,3) \to (3,3)$ 的格子值为 $1,10,0,4,8$，即使跳过 $10$ 也只能得到 $1+4+8=13$，不如 $15$。

样例2

输入

2 2 1
1 1 2 2
1 2
3 4

输出

-1

说明

终点相对起点至少要走 $2$ 步，初始体力只有 $1$，无法到达终点，输出 $-1$。起点的符文不能当作通关得分。