题目描述

击败恶龙后，小$B$获得进入宝藏空间的机会，里面遍布奇珍异宝，也暗藏陷阱。

宝藏空间是一个$n×m$的矩形地图，每个位置上有一个整数 $val_ij$，若$val_ij$不等于0，表示该位置上有价值为的宝藏（宝藏最多只能被收集一次），否则表示该位置是一个黑洞陷阱，一进入就会被吸走！

刚开始小B被传送到了$(sx,sy)$的位置，每秒小B可以走到上下左右相邻的四个位置并收集对应的宝藏，或留在原地，在收集宝藏的同时，他必须在p秒内赶到空间的出口$(ex,ey)$，否则出口将关闭，小B将永远困在宝藏空间里。

你提前拿到了宝藏空间的地图，请你帮帮小B，若小B不能在p秒内到达终点，输出"Don't go!"，否则输出最多能收集到的宝藏价值（不包含起点处的宝藏价值）。

输入格式

第一行三个正整数，$n,m,p$；

第二行四个正整数，$sx,sy,ex,ey$，依次表示起点、终点的横纵坐标；

接下来的n行，每行m个整数$a_ij$：

当$a_ij$不等于$0$时，表示第$i$行第$j$列的宝藏价值；

当$a_ij$等于$0$时，表示第$i$行第$j$列是黑洞陷阱。

输出格式

一行，输出$p$秒内从起点$(sx,sy)$到终点$(ex,ey)$，最多能收集的宝藏价值（不包含起点处的宝藏价值），若不能到达终点，输出$"Don't go!"$。

输入样例

2 2 2
1 1 2 2
1 2
3 5

输出样例

8

样例分析

从$(1,1)$移动到$(2,1)$获得价值为$3$的宝藏，从$(2,1)$移动到$(2,2)$获得价值为$5$的宝藏，总价值为$8$。

数据规模

对于$100$的数据，

$1≤n,m,k≤200$，$-10^6≤a_ij≤10^6.$

这题有解吗，我的记忆化搜索被自己卡掉了（TLE）