带预算的地砖路线

难度：T4

【知识点：网格最短路】

前置知识：四邻接、非负费用、优先队列。

题目描述与输入

首行 $H,W,B$，随后 $H$ 行每行 $W$ 个整数。$0$ 是墙，其余数为进入该格的费用；只能四邻接移动。起点左上、终点右下均不是墙，起点不收费。求预算内从起点到终点的最小费用。

输出格式

输出最小费用，无法到达或超过预算输出 $-1$。

数据范围

$1\le H,W\le30$，$0\le B\le10^6$，非墙格费用在 $[1,9]$ 内。

样例输入

2 3 10
1 9 1
1 1 1

样例输出

3

样例解释

经左下、中下、右下费用$3$，预算$10$足够。