Warriors Gumball goes to a maze which has N * M cells.
There are seven monsters in this maze, numbered from 0 to 6. Each monster has HP and ATK.
There are 4 types of buff in the maze：
1. ATK buff : increase Ab attack point (ATK)
2. DEF buff : increase Db defense point (DEF)
3. HP buff : increase Hb health point (HP)
4. MP buff : increase Mb magic point (MP)
Warriors Gumball is a great Gumball. At first he has As ATK, Ds DEF, Hs HP and Ms MP. And he can use 3 types of magic:
1. Drainage of magic : increase Hm HP
2. Light spells : increase Am ATK
3. Earth magic : increase Dm DEF
Each magic which Warriors used will consume Mm MP.
The meaning of the symbols in the maze:
'S' : initial position of Warriors Gumball, ‘S’ only appear once.
'#' : obstacle, can't move to this cell
'.' : empty, can move to this cell
'A' : ATK buff
'D' : DEF buff
'H' : HP buff
'M' : MP buff
'0' - '6' : denotes monster. This cell can be moved in only if this monster is killed.Each number only appear once.
Each step Warriors Gumball can move in four directions(up, down, left, right).
If Warriors Gumball want to kill a monster, he will attack monster.
In every attack, If Warriors Gumball's DEF not less than monster’s ATK, He will not get hurt. Otherwise Warriors Gumball's HP will reduce the value equivalent to the difference between monster's ATK and Warriors Gumball's DEF. monster's HP will reduce the value equivalent to Gumball's ATK. Warriors Gumball’s HP and monster’s HP will reduce at the same time.
If the monster's HP reduced to less than or equal to 0, the monster will die.
But if Warriors Gumball's HP reduced to less than or equal to 0, he will die and game over.
He wants to know the maximum HP can be remained when he kill all monsters(When all the monsters are killed, you can still explore the maze). Can you help him?
Input
The first line is an integer T which indicates the case number.
And as for each case, first line is two integer N and M which indicates the size of maze.
Next N line, each line M character which indicates the maze.
Next seven line, each line is two integer A and H, which indicates the monsters ATK and HP
Next line is four integer As, Ds, Hs, Ms which indicates Warriors Gumball initial state
Next line is four integer Am, Dm, Hm, Mm which indicates information of magic
Next line is four integer Ab, Db, Hb, Mb which indicates information of buff
Limit
$1 \leq T \leq 20$
$1 \leq N, M \leq 100$
$1 \leq Ai, Hi \leq 20$
$1 \leq As, Ds, Hs, Ms \leq 100000$
$1 \leq Am, Dm, Hm, Mm \leq 100000$
$1 \leq Ab, Db, Hb, Mb \leq 100000$
Output
As for each case, you need to output one integer which indicate the answer.
If Warriors Gumball can’t achieve goal, output -1.