题目描述

给定一个$n * m$的网格地图，格子有三种情况：

1. ‘.’ 表示空，可以正常通行

2. ‘#’ 表示有墙，不能通行

3. 大写英文字母（$A-Z$）表示有陷阱，可以通行，但经过会扣一定的血量，并且不会消失

一共有$k$个陷阱（编号从$A$开始，$ABCDE...$），$k<=26$，并且给定起点，终点， 和初始血量$H$，行走方向只有上下左右四个方向，注意在行走过程中不能有任意 时刻的血量小于等于$0$。输出到达终点的最大血量。

输入格式

输入一共有$n+k+2$ 行，

第一行依次为$n, m, k, H$。其中$n≤100，m≤100, k≤26, H≤200$。

第二行四个整数，表示起点的行、列坐标和终点的行、列坐标。棋盘从左往右依 次是$1…m$ 列，从上倒下依次是$1…n$ 行。数据保证起点和终点所在的格子都是空的。

接下来$n$ 行，每行一个长度为$m$ 的字符串，表示棋盘的情况。 .表示为空，#表 示为墙，$A-Z$ 的字符表示陷阱的种类。

接下来$k$ 行

接下来的第$1$ 行，一个数表示$A$ 代表的陷阱扣多少血；

接下来的第$2$ 行，一个数表示$B$ 代表的陷阱扣多少血；

……

接下来的第$k$ 行...

以此类推，扣的血量小于等于$200$。

输出格式

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

样例数据

输入1

5 5 2 15
1 1 5 4
....A
####.
.....
###B#
.....
9
3

输出1

3

输入2

5 5 2 10
1 1 5 4
....A
####.
.....
###B#
.....
9
3

输出2

-1

数据规模与约定

对30%的数据，$n<10, m<10, k=0$。

对70%的数据，$n<10, m<10, k<10$。

对100%的数据，$n≤100，m≤100, k≤26$。

注意：起点和终点都是给定的