题目描述

小Q来到杭州西湖博物馆游玩，恰逢亚运时间，有很多需要帮助的外国友人也在馆内。小Q要从博物馆入口进入，逛到出口。虽然他有点懒，但他很善良，路上只要遇到了需要帮助的外国人，就一定会出手相助，并耗费一定的精力。同时，帮助不同的外国人难易程度不同，耗费小Q的精力数量也不同。请你找到一条路线，使得小Q从入口走到出口，能保留最大的精力。

给定一个n*m的博物馆地图，地图中的格子有三种情况：

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

2.‘#’表示不能通行

3.大写英文字母（A~Z）表示有外国人，可以通行，但经过会消耗一定的精力。

一共有k个外国人（编号从A开始，ABCDE...），k<=26，并且给定入口，出口，

和初始精力H，行走方向只有上下左右四个方向，注意在行走过程中不能有任意

时刻的精力小于等于0。输出到达出口的最大精力。

Input

从文件play.in中读取数据。

输入一共有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 .

Output

输出到文件play.out中

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

Samples

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

3

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

-1

Limitation

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

其中40%的数据，n<10, m<10, k<10。

其中30%的数据，n≤100，m≤100, k≤26。

注意：入口和出口都是给定的