Maybe many one have played or at least heard of The Family Computer(FC). And this problem is mainly about a classical game named "Ice Climber"
In this game, our little Eskimo wants to climb higher and catch the big bird at last. In the climbing, little Eskimo may be faced with many troubles, like enemy or wall.
The game field made up with several floors and floors are seperated by many pieces of bricks. The number of pieces between different floors and different positions are different. There may also be enimies and walls on these bricks. By jumping up Eskimo can decrease the number of pieces on the ceiling of his position or even jump to another floor.
Each time Eskimo can choose on of the following steps:
Move left or right one block as long as the block is empty and the block has supporting pieces of bricks, using t1 time.(That is, there will not be an enemy or a wall on the block and the block has at least one bricks)
Jump up and destroy one piece of brick of the ceil just above little Eskimo or Jump up to an upper floor if all bricks on the ceiling of his current position have been cleared. If he jumps to the next floor he can choose to land on either the left or the right adjacent position as long as there are no enimies or walls on them (Of course there must also be at least a supporting brick at that position). Both kind of jumping takes t2 time.
Knock off one little enemy just next to little Eskimo in t3 time, and the enemy will disappear.
Each block has several pieces. And only if the number of the pieces of the block is 0 can little Eskimo jump up through it to the next floor. Sometimes Eskimo may clear all the bricks of ceiling of a position where there is an enemy standing on it, in these cases this unlucky enemy will be cleared at once. If on the next floor, above one block there is a wall, then Eskimo can never jump up through this block no matter how much pieces it has even zero. If little Eskimo jumped up to the next floor successfully, for instance through the ith position, he can choose to land on either to the left, the i-1th block or to the right, the i+1th block as you like, but not the ith block itself. And you can never jump over the enemy or the wall or the zero pieces blocks.
And in the whole process, little Eskimo can not land on to the side, that is, he can not land on to the 0th block or the w+1th block. Also, he cannot land on to where there are only zero pieces blocks or blocks with an enemy or blocks with a wall. And while moving, he cannot get to the 1st block from the nth block, or get to the nth block from the 1st block.
And just like the picture below, the 2nd floor's floor is the 1st floor's ceil:
picture
Now, we have n floors, and each floor has the same width of w blocks, but the number of the pieces of each block can be different. Thus, we can get a map of these floors. Little Eskimo starts from the leftest block on the first floor, unlike the picture above, and we want to use the minimum time to get to the nth floor.(Any block on the nth is all right)
Input
The input contains multiple cases.
In each case, the first line contains two integers represents n and w.(1<=n<=2000 , 1<=w<=100)
The second line contains three integers represents t1, t2, andt3.(0<=t1,t2,t3<=100)
Then the 2n lines, the odd lines contains w characters, describing what is on the floor: '#' represents the enemy, which we assume does not move, '|' represents wall, and '0' represents the block is empty. While the even lines contains w digits from '0' to '9' representing the number of the pieces of each block.
[Notice]: the map inputs from the nth floor downto the 1st floor, that is, the first line of this map describes what is on the nth floor, and the second line of this map describes the number of the pieces of each block of nth floor, or the n-1th floor's ceil.
Output
In each case, output one line with an integer representing the minimum time little Eskimo can get to the nth floor. If there is no way to get to the nth floor, output -1.
Sample Input
This sample input just describe the picture above.
5 22
1 2 3
0000000000000000000000
2222212222122222221222
0000000000000000000000
2122222122222221112222
000000000000000000000#
2222212221222222222111
0000000000000000000000
2222222222112222222221
0000#00000000000000000
1111111111111111111111
Sample Output
23
