Buggy Robot

A robot sits in a two dimensional grid. Each cell of the grid is an empty cell, an obstacle, the robot's starting cell, or the exit. An empty cell is written as ., the robot's starting cell as S, an obstacle as #, and the exit as G. Exactly one cell is the exit, and the robot leaves the grid the moment it steps on that cell.

You drive the robot by sending it a command string. The string consists only of the four characters L (move one cell left), U (move one cell up), R (move one cell right), and D (move one cell down). If the target cell holds an obstacle or lies outside the grid, the robot ignores that command and carries on with the commands that follow.

Your friend already sent a command string to the robot, but the string does not necessarily bring the robot to the exit.

You want to fix the string so that the robot steps on the exit cell. The robot stops the moment it steps on the exit, so it never runs the commands left after that.

You can fix the string with two operations. You can insert one command at any position, and you can delete one command. Find the minimum number of operations needed to make the robot step on the exit.

The first line contains the number of rows $N$ and the number of columns $M$ of the grid ($1 \le N, M \le 50$).

Each of the next $N$ lines contains a string of exactly $M$ characters. Every character is . (empty), S (the robot), # (an obstacle), or G (the exit). The grid holds exactly one S and exactly one G, and a path from the robot to the exit always exists.

The last line contains the command string $s$ ($1 \le |s| \le 50$). The string $s$ consists only of L, R, U, and D.

Print, on one line, the minimum number of operations needed to fix the command string so that the robot steps on the exit.