On the way to the Dragon's Castle, there is an Ice Valley. Now Lott wants to pass through the Ice Valley. While in the Ice Valley, there was a lot of treasure, and the treasure can be helpful to Lott, so Lott wants to get as many treasure as he can.
Now, Lott has reached the Ice Valley, and he finds that the Ice Valley is made up of n*m blocks. And on the blocks there are different signs. Lott has been told by friendly NPC that the meaning of each signs:
The meaning of each signs:
Nothing: The block is an empty ground, you step on it and then you can choose to go up, down, left, right as you like. However the number of this kind of block is very few no more than 100.
Arrow: The block has magic power, you step on it and you have to go to the next block in the same direction as the arrow.
Wall: The block is a wall, and you can never step on it.
Box: The block has a box with treasure, you step on it and you can open the box to get the treasure, then, you can go up, down, left, right as you like. The number of the box in the valley is always no greater than 10.
Hole: The block is a trap, and you will die if you step on it.
Now, Lott starts at the entrance of the valley x1, y1. He wants to get to the exit at the position of x2, y2. And at the same time, Lott wants to get the most treasure he can. The entrance and the exit are both signed nothing. The entrance and the exit can be the same positions.
Now, we assume that each movement from one block to another costs 1 second and each opening of one box spends 2 seconds, and we want to know the minimum time Lott uses to pass through the valley with the most treasure.
Input
There are multiple cases.
In each cases, the first line contains two integers n , m. (1<=n<=500 , 1<=m<=500)
Then n lines with m characters describing the valley. And '0' represents nothing; 'L','U','D','R' represents arrow with the direction of left, up, down, right; 'W' represents a wall; '$' represents a box with treasure; '#' represents the trap hole.
Then the last line with four integer x1, y1, x2, y2. (1<=x1<=500 , 1<=y1<=500 , 1<=x2<=500 , 1<=y2<=500)
Output
Of each case, output one line with one integer representing the minimum time Lott will use, if he cannot pass through the valley, output -1.
Sample Input
5 5
DL0R$
DWDWD
DL$LL
D#DWU
RURR0
1 3 5 5
5 5
0RRRD
UW$#D
UD0UD
U#$WD
ULLLL
1 1 3 3
Sample Output
14
-1
