问题说明

小未在玩一款武侠游戏，游戏里PK不仅要有高超的操作和智慧，还要有很牛的装备。现在他进入了一个副本，副本里面有极品15星的装备宝箱，但是从副本入口到宝箱有很多条路，当然不可能轻轻松松的拿到极品装备。一路上会随机刷出各种攻击力很强的怪物。它会攻击小未的角色，当然也必须打败它才能通过，这个过程角色的血量HP会减少(血量不会回复)，预先给你副本的地图，请你帮小未计算一下能不能拿到极品装备。

注意：刚进入副本时角色是满血的，中途没有任何回血的措施，在过程中血量hp必需>0,不然副本结束(即拿不到极品装备)。

输入格式

输入一共有 n+k+2 行，
第一行依次为 n, m, k, H，分别表示副本行列数，怪物数，角色的满血血量。其中 n≤100，m≤100, k≤10, H≤200。
第二行四个整数，表示副本入口坐标和宝箱所在坐标。数据保证起点和终点所在的格子都是 空的。
接下来 n 行，每行一个长度为 m 的字符串，表示副本地图。‘.’表示可走，#表 示为不可走，A-Z 的字符表示怪物种类
接下来 k 行
接下来的第 1 行，一个数表示 A 怪物会使角色扣多少血；
接下来的第 2 行，一个数表示 B 怪物会使角色扣多少血；
……
接下来的第 k 行...
以此类推，扣的血量小于等于 200。

输出格式

输出共一行，表示到达终点最后最多剩下多少血。如果不能拿到装备，则输出game over

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

3

来源/分类