Buggy Robot

문제

There is a robot in a 2D grid. The grid consists of obstacles, and there is exactly one cell that is the exit. The robot will exit the grid if it ever reaches the exit cell. Empty cells are denoted as '.', the robot's initial position is denoted as 'R', obstacles are denoted as '#', and the exit is denoted as 'E'.

You can program the robot by sending it a series of commands. The series of commands is a string consisting of characters 'L' (move one square left), 'U' (move one square up), 'R' (move one square right), or 'D' (move one square down). If the robot would run into an obstacle or off the edge of the grid, it will ignore the command (but it will continue onto future commands, if there are any).

Your friend sent a series of commands to the robot, but unfortunately, the commands do not necessarily take the robot to the exit.

You would like to fix the string so that the robot will touch the exit square. (Note: once the robot reaches the exit, it stops, even if there are more commands in the string.)

You can fix the string with a sequence of operations. There are two operations: inserting a command or deleting a command. What is the minimum number of operations you would need to fix the program?

입력

The first line of the input contains the two integers $NN$ and $MM$, $1\le N,M\le 501\; \backslash le\; N,\; M\; \backslash le\; 50$, which are the width and height of the grid.

The next $NN$ lines will contain a string of exactly $MM$ characters, each of which is '.' (empty), 'R' (the robot), '#' (an obstacle), or 'E', the exit. There will be exactly one 'R' and one 'E' in the grid, and it will always be possible to navigate the robot to the exit.

The last line contains a string $ss$ ($1\le \mathrm{\mid }s\mathrm{\mid }\le 501\; \backslash leq\; |s|\; \backslash leq\; 50$) of commands. The string $ss$ will consist only of 'L', 'R', 'U', and 'D'.

출력

Print one line containing the single integer indicating the minimum number of operations necessary to fix the command string so that the robot makes it to the exit.

3 3
S..
.#.
..G
DRRDD

1

3 7
.......
.G.#.S.
.......
LDLDLLDR

1

3 7
.#.....
.G.##S.
.......
LDLDLLDR

2

2 4
S.#.
#..G
RRUUDDRRUUUU

0