描述 Description

魔法师小F来到了沙漠，他希望通过沙漠去挑战邪恶的魔法师。
这个是一个n*m的矩形沙漠，除了北面和南面，西边和东边都是特别高的大山，小F不会爬山。
沙漠中，每个地方都有一个邪恶魔法师召唤的邪恶的生物，每个生物都有自己的属性，“攻击力，防御力，血量”，当然，
小F同样也有“攻击力，防御力，血量”这3个属性，而且小F可以召唤其他生物来协助自己作战，被召唤的生物也有“攻击力，防御力，血量”
这3个属性。如果某个怪物的血量为0或者更少，那么就是一具尸体，小F可以轻松踏过尸体。

当小F或者小F的召唤兽和怪兽战斗的时候，每个回合都是小F或者小F的召唤兽先攻击，然后怪兽攻击，然后小F或者小F的召唤兽继续攻击，然后怪物再攻击，直到一方死去。 「战斗是不死不休的！」 当然，每和一个怪兽战斗，小F最多只能召唤一个召唤兽，不然会浪费太多的魔力。
但是召唤兽都很懒，所以他们最多只能被召唤一次（如果本回合用过这只召唤兽，那么下一回合召唤兽也不能被召唤）。 如果召唤兽被怪物杀死了，在战斗中，怪兽可能会掉血，那么小F可以亲自收拾残局，即接着怪物剩余血量和怪兽战斗。  只要怪兽不死，那么小F就不能走到被怪兽所占据的地方。小F希望保留最多的血通过沙漠（到达沙漠的南边），因为对面还有邪恶的魔法师等着他，因为沙漠缺水，小F节约时间不能在地图中东西走，也不能回头（即往北走），每次可以在当前位置向南（下），或者西南（左下方），东南方向（右下方），

战斗：
小F方单位攻击对方，对敌方单位造成 max(小F方攻击力-敌方防御力,0)的伤害。
敌方单位攻击小F方，对小F方单位造成 max(敌方攻击力-小F方防御力,0)的伤害。
小F方单位攻击对方，对敌方单位造成 max(小F方攻击力-敌方防御力,0)的伤害。
敌方单位攻击小F方，对小F方单位造成 max(敌方攻击力-小F方防御力,0)的伤害。
……
直到一方死亡(血量少于等于0为死亡)。
你可以认为如果小F和召唤兽同时攻击怪兽，只是召唤兽在和怪兽攻击，当召唤兽死了，那么小F在和怪兽战斗。
(总是小F的单位先攻击，如果攻击力低于对方防御力，那么无法对对方造成伤害，那么无法攻击对方，如果双方都无法攻击对方，那么小F只好不走这条路了)

输入格式 InputFormat

第一行2个数字: n,m,表示沙漠南北跨度，和东西跨度。

例如：当n=2 m=3时，地图为：

北
=====
西  |xxx|
|xxx|  东
—–
南
“x”表示怪兽
“|”表示大山，无法到达
“=”表示初始位置，为任意选择
“-“表示离开沙漠的位置，可以任意选择（只有沙漠中有怪物）

下面n行，每行m个数字，表示地图对应位置怪物的攻击力
下面n行，每行m个数字，表示地图对应位置怪物的防御力
下面n行，每行m个数字，表示地图对应位置怪物的初始血量
下面一行有3个数字，表示小F的攻击力，防御力，初始血量
下面一行一个数字p，表示小F拥有的召唤兽数量
下面p行，每行3个数字，分别为一个召唤兽的攻击力，防御力，血量

输出格式 OutputFormat

一行一个数字，表示小F最多剩余血量。如果小F无法活着走出沙漠，那么就输出-1

样例输入 SampleInput

样例输出 SampleOutput

数据范围和注释 Hint

数据范围：
0<=p<=10
0<=攻击力，防御力<=100
0<=怪物血量,召唤兽血量<=2000
0<=小F血量<=2^30

第一组数据满足  p=0,m=1
第二组数据满足  p=10,m=1
第三组数据满足  m=3
第四组数据满足  1<=n,m<=50,p=0
第五组数据满足  1<=n,m<=50,p=3
其余数据满足  1<=n,m<=50,p<=10