给定一个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。

【数据规模】

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

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

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

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