3043: 刀塔大师lwq 3

在$lwq$使用剑圣补满$1W$刀，解锁“野见愁”成就之后，将矛头转向了新出的$RPG$“丛林乱斗”。这次，$lwq$选择到了他的绝活英雄------“灰烬之灵”。

游戏地图可以简化为一个$n*m$的矩阵，$lwq$的初始血量为$h$，攻击力为$1$。地图上存在$k$个怪物，第$i$个怪物的攻击力为$a_{i}$，血量为$1$。$lwq$可以向上下左右四个位置移动，每移动一次花费一个单位的时间。地图上存在一些障碍，$lwq$无法跨过这些障碍。

地图上某个位置出现了空投，$lwq$十分想要用空投来改变自己的命运。于是，$lwq$朝着空投的位置出发。$lwq$如果想要跨过第$i$个怪物，就要打败它并减少$a_{i}$点生命值。打败怪物消耗的时间忽略不计。一旦$lwq$ 打败了某个怪物，再通过这个位置时就不用再次战斗了。任意时刻$lwq$的生命值必须为正。$lwq$ 十分着急，请问$lwq$ 到达空投点最少需要多少单位时间。若不能到达，则输出“-1”。

输入第一行为一个整数$T(T \leq 30)$，表示一共有$T$组测试数据。

对于每组测试数据：
第一行有四个整数$n,m(1 \leq n,m \leq 50)$,$h(1 \leq h \leq 10^6)$,$k(1 \leq k \leq 9)$，分别表示矩阵的大小，初始血量和怪物数量。

第二行有$k$个整数，其中第$i$个整数$a_{i}(1 \leq a_{i} \leq 10^6)$，表示第$i$个怪物的攻击力。

接下来是一个n*m的矩阵，其中$s$表示$lwq$的初始位置，$t$表示空投位置，$1$$\sim$$k$为表示怪物位置，$\#$表示障碍，.表示可以通行的路。

对于每组测试数据输出一个整数$x$，表示$lwq$到达空投所需的最低单位时间。若不可能，输出“-1”。

1
3 3 5 2
2 6
s.1
.#.
2.t

4