给定一个 $n \times m$ 的网格地图，格子有三种情况：
1. '.' 表示空，可以正常通行。
2. '#' 表示有墙，不能通行。
3. 大写英文字母（ A ~ Z ）表示有陷阱，可以通行，但经过会扣一定的血量，并且不会消失。
一共有 $k\ (k \leq 26)$ 个陷阱（编号从 A 开始，ABCDEFGHIJK），并且给定起点，终点和初始血量 $H$，行走方向只有上下左右四个方向，注意在行走过程中不能有任意时刻的血量小于等于 $0$。输出达到终点的最大血量。

输入一共有 $n + k + 2$ 行。
第一行依次为 $n,\ m,\ k,\ H$。其中 $n \leq 100,\ m \leq 100,\ k \leq 26,\ H \leq 200$。
第二行四个整数，表示起点的行、列坐标和终点的行、列坐标。棋盘从左到右依次是 $1\ ...\ m$ 列，从上到下依次是 $1\ ...\ n$ 行。数据保证起点和终点所在的格子都是空的。
接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示棋盘的情况。 . 表示为空， # 表示为墙， A - Z 的字符表示陷阱的种类。
接下来 $k$ 行。
接下来的第 $1$ 行，一个数字表示 A 代表的陷阱扣多少血；
接下来的第 $2$ 行，一个数字表示 B 代表的陷阱扣多少血；
...
接下来的第 $k$ 行...
以此类推，扣的血量小于等于 $200$。

输出共一行，表示达到终点最后最多剩下多少血。如果不能到达终点，则输出 $-1$。

对于 $30\%$ 的数据，$n < 10,\ m < 10,\ k = 0$。
对于 $70\%$ 的数据， $n < 10,\ m < 10,\ k < 10$。
对于 $100\%$ 的数据，$n \leq 100,\ m \leq 100,\ k \leq 26$。
注意：起点和终点都是给定的。