题目描述
YMDragon 听说大家都喜欢玩魔塔，所以他自己做了个给大家玩。
不过，由于他太垃圾啦，只能做出某一层的地图，而且这个地图仅包含以下地形：
@：墙(Wall)，不可通行。
.：通道(Road)，可以通行。
M：怪物(Monster)，可以通行，但第一次通行时必须先打败怪物。
P：玩家(Player)，可以通行，作为玩家的出生地点。
H：血瓶(Healing salve)，可以通行，第一次通过时获得该血瓶（自动增加相应的生命值）。
D：门(Door)，可以通行，但第一次通行时需要消耗一枚钥匙。
K：钥匙(Key)，可以通行，第一次通过是获得该钥匙。
J：宝石(Jewel)，可以通行，第一次通过时获得该宝石（自动增加相应的防御值）。
E：出口(Export)，可以通行，走到出口时自动结束游戏并进行评分。
YMDragon 规定，玩家出生在某个给定的点上，并最终要走到出口(Export)。最后评分时，玩家的剩余生命值越多，分数就越高。
现在，YMDragon 把魔塔交给了你。当然，你要尽可能地获得更高的分数，不然 YMDragon 会认为你在敷衍他而不高兴的。
输入格式
第一行两个整数 $R$ 和 $C$，描述地图的大小，并规定左上角为 $(1,1)$，右下角为 $(R,C)$。
接下来 $R$ 行，每行 $C$ 个字符描述地图。字符仅含有题面中的 $9$ 种字符。
接下来若干行描述血瓶，每行三个整数 $x$，$y$，$val$，描述一个位置在 $(x,y)$ 的，生命值为 $val$ 的血瓶，以一行三个 $0$ 结束。
接下来若干行描述宝石，每行三个整数 $x$，$y$，$val$，描述一个位置在 $(x,y)$ 的，防御值为 $val$ 的宝石，以一行三个 $0$ 结束。
接下来若干行描述怪物，每行四个整数 $x$，$y$，$a$，$b$，描述一个位置在$(x,y)$的怪物，且初始情况下，玩家需要用 $a$ 回合才能消灭该怪物，每回合怪物对玩家造成 $b$ 点伤害，以一行四个 $0$ 结束。
最后一行一个正整数，描述玩家的初始生命值（没有上限）。
输出格式
第一行一个整数 $K$，表示你的行动步数。
接下来 $K$ 行，每行两个整数 $x,y$，表示在本次移动中，你移动到了 $(x,y)$，每次你只能向相邻的四个格子移动。
你输出的 $K$ 不能超过 $3*10^6$，且最终你必须停留在出口(Export)，且生命值必须一直是正数。
样例
样例输入 1
3 3
E.P
D@J
HKM
Healing salve:
3 1 10
0 0 0
Jewel:
2 3 2
0 0 0
Monster:
3 3 10 2
0 0 0
Player:
351样例输出 1
6
2 3
3 3
3 2
3 1
2 1
1 1提示
初始情况下的防御值为 0，每回合怪物实际造成的伤害为 $max$(0,初始情况伤害-防御值)。
