最近WS因差1分钟没能AK而深受打击，自(bi)暴(guan)自(xiu)弃(lian)，沉迷英雄(shua)联盟(ti)无法自拔，有天WS突发奇想，准备开发一款英雄联盟版的迷宫游戏，游戏规则如下:
英雄盖伦出生在迷宫的某处，盖伦可往前后左右四个方向走动，每走一步用时为1(也可停止不动)，盖伦带有技能闪现，使用闪现可以穿过1个厚度的墙(耗时为1，穿完墙落地开始闪现进入CD)，闪现技能CD为p，迷宫中随机分布0-3个蓝爸爸，经过蓝爸爸时可以选择打或者不打，击杀蓝爸爸消耗1单位时间并可获得蓝buff(蓝爸爸不会复活)，蓝buff持续时间为q，buff持续时间内使用闪现技能CD减半(向下取整，如果我击杀蓝buff时候技能还处于cd状态cd不会减半)，多个蓝buff时间可叠加。请写出一个程序求出盖伦走出迷宫所需的最小时间。
ps：buff剩一秒时穿墙后闪现CD按原CD计算。
输入包含多个测试下样例，每个样例的第一行包含4个整数m,n,p,q。分别表示迷宫的长，宽，闪现CD，每个蓝buff持续时间，1<=m,n<=20,1<=p,q<=10。接下来的m行为迷宫分布，＃表示墙，.表示路，@表示蓝爸爸，S表示英雄出生点，E表示迷宫出口。
(测试数据保证至少有一条路可以通向出口)
输出一个数字表示盖伦走出迷宫所需的最小时间
1 10 1 5 S.#..#..#E 1 10 2 5 S.#..#..#E 1 10 2 5 S@#..#..#E
6 8 7