미로 Batch 컴파일 명령

심심한 지학이는 승현이가 만들고 있다는 $N \times N$ 크기의 미로를 입수해 냅니다. 미로는 격자판 형태로 만들어졌으며, 몇 개의 칸은 막혀 있을 수도 있습니다. 지학이는 또한 승현이가 미로에 투입한 로봇의 이동 경로 역시 가지고 있습니다. 경로의 길이는 $k$ (인접한 칸으로 $k$번 이동)이지만, 로봇이 어디서 출발했는지는 알 수 없습니다. 알고 있는 것은 로봇이 막히지 않은 칸에서 출발했다는 사실뿐입니다. 지학이는 심심하기 때문에 로봇의 출발지를 알고자 합니다. 지학이가 선택할 수 있는 유일한 방법은 출발 가능한 모든 칸에서 주어진 경로대로 이동해 보는 것입니다. 만약 출발지가 여러 개거나 존재하지 않는다면 뭔가 잘못되었겠죠.. 그러나 시험 삼아 작은 미로들을 만들어 이 작업을 하던 지학이는 대부분의 경우 주어진 이동 경로의 앞부분만 따라서 이동해도 출발지를 명확하게 결정할 수 있다는 것을 알게 되었습니다. 이제 지학이는 그 '앞부분'의 길이를 찾아 출발지를 찾고자 하네요. 지학이를 도와줍시다.

입력 형식

첫 번째 줄에 두 개의 정수 $N$ ($1 \le N \le 100$)과 $k$ ($0 \le k \le 10^{5}$)가 공백을 사이로 두고 주어집니다. 다음 $N$개 줄에는 승현이가 제작하는 미로의 지도가 주어지는데, 각 줄에는 0 또는 1로만 구성된 길이가 $N$인 문자열이 주어집니다. 입력의 $i+1$행 $j$열의 문자가 0이라면 미로의 $i$행 $j$열은 열려 있고, 1이라면 막혀 있습니다. ($1 \le i,j \le N$) 마지막 줄에는 로봇의 이동 경로를 나타내는 길이가 $k$인 문자열이 주어집니다. 각 문자는 매 순간 로봇이 어떤 방향으로 한 칸 이동했는지를 나타냅니다. 문자가 L이면 바로 왼쪽, R이면 바로 오른쪽, U이면 바로 위, D이면 바로 아래로 이동했다는 것입니다. 마지막 줄의 각 문자는 U, D, L, R 중 하나임이 보장됩니다.

출력 형식

출발지를 명확하게 결정하기 위해서 지학이가 모든 출발 가능한 칸에서 이동해야 할 주어진 경로의 앞부분의 길이의 최솟값을 출력합니다. 만약 주어진 경로가 유효하지 않거나 답이 없다면, -1을 출력합니다.

입출력 예제