버그 로봇

2차원 격자에 로봇 한 대가 있다. 격자의 각 칸은 빈 칸, 장애물, 로봇의 출발 칸, 출구 중 하나다. 빈 칸은 ., 로봇의 출발 칸은 S, 장애물은 #, 출구는 G로 나타낸다. 출구는 정확히 한 칸이고, 로봇이 출구 칸을 밟는 순간 격자를 빠져나간다.

로봇에게 명령어 문자열을 보내서 로봇을 움직인다. 명령어 문자열은 L(왼쪽으로 한 칸), U(위로 한 칸), R(오른쪽으로 한 칸), D(아래로 한 칸) 네 문자로만 이루어진다. 이동할 칸이 장애물이거나 격자 밖이면 로봇은 그 명령을 무시하고, 뒤에 남은 명령을 그대로 이어서 수행한다.

친구가 이미 로봇에게 명령어 문자열을 보냈지만, 그 문자열이 로봇을 출구로 데려간다는 보장은 없다.

로봇이 출구 칸을 밟도록 문자열을 고치려고 한다. 로봇은 출구를 밟는 순간 멈추므로, 그 뒤에 남은 명령은 수행하지 않는다.

문자열은 두 가지 연산으로 고칠 수 있다. 명령 하나를 원하는 위치에 삽입하거나, 명령 하나를 삭제한다. 로봇이 출구를 밟게 만드는 데 필요한 연산의 최소 횟수를 구하라.

첫째 줄에 격자의 행 수 $N$과 열 수 $M$이 주어진다 ($1 \le N, M \le 50$).

다음 $N$개의 줄에는 길이가 정확히 $M$인 문자열이 주어진다. 각 문자는 .(빈 칸), S(로봇), #(장애물), G(출구) 중 하나다. 격자에는 S와 G가 각각 정확히 하나 있고, 로봇에서 출구까지 가는 경로는 항상 존재한다.

마지막 줄에 명령어 문자열 $s$가 주어진다 ($1 \le |s| \le 50$). $s$는 L, R, U, D로만 이루어진다.

로봇이 출구를 밟도록 명령어 문자열을 고치는 데 필요한 연산의 최소 횟수를 한 줄에 출력한다.