某天某gouhuizhang想要在机房找人去约会，大家吓的四处乱串。为了逃避约会，大家需要在机房合成秘宝隐身衣。
其实机房是一个n*m的矩阵，标记为'.'的格子可以任意移动，标记为'#'的格子是障碍物，你所在的起点标号为'S'。众(wo)所(xia)周(bian)知(de)，合成隐身衣需要三瓶快乐水，分别位于标号为'X'，'Y'，'Z处。唯一可以合成隐身衣的地方在标号为'E'处。
你每秒只能移动一个单位的距离，每次只能选择向上下左右四个方向移动。每次移动消耗1体力值。
你不能移动到矩阵外面去！神奇的快乐水还有着神奇的原力哦。快乐水X，Y，Z对应的原力分别为a，b，c。带着快乐水移动每步所需要的消耗为你携带的快乐水中原力的最大值加上固定体力消耗值1。
点可以重复经过，路过位于快乐水的格子时你可以选择拿起或不拿起。但是快乐水只要拿起就不能放下。
狗急都会跳墙，so当你没有集齐三瓶快乐水时，你是可以移动到障碍物上面去的。但是你一旦集齐三瓶快乐水，你就不能移动到障碍物上！！！
为了逃避约会，请聪明的你帮助大家计算合成隐身衣的最小体力值消耗是多少？

第一行输出t，代表数据组数。()
每组数据的第一行两个整数表示n,m()。
接下来n行，每行m个字符，描述机房地形。
下面一行三个整数a, b, c()。

对每组数据输出合成隐身衣的最小体力值消耗(保证有解)。

4
3 5
##S##
X#Y#Z
##E##
1 5 4
2 4
SXY#
E..Z
3 2 1
2 4
SXY#
E..Z
1 2 3
3 5
S.##Z
X#Y.#
##E.#
1 5 3

27
19
21
29

第一组样例最佳解法：S -> X –> Z -> Y -> E。
路线为：(1,3),(2,3),(2,2),(2,1),(2,2),(2,3),(2,4),(2,5),(2,4),(2,3),(3,3)。
答案为27。