놀이공원 대기줄

미르코와 슬라브코는 쉬는 날에 놀이공원을 구경하기로 했다. 이 놀이공원에서 가장 인기 있는 놀이기구는 워터 슬라이드이고, 입구 앞 대기줄은 언제나 사람으로 가득 차 있다.

대기줄은 격자 위의 칸을 한 줄로 이어 놓은 모양이다. 줄의 시작은 1번 칸, 끝은 $L$번 칸이다. 아래 그림은 $12$분을 기다려야 하는 대기줄의 배치이며, $L = 12$와 경로 문자열 RRRRDLLLLDD에 해당한다.

미르코가 줄에 들어섰을 때 앞의 자리는 모두 차 있었다. 1분이 지나면 줄의 끝에 있는 사람이 슬라이드에 올라타고, 줄에 서 있는 모두가 한 칸씩 앞으로 옮겨 가고, 새로운 사람 한 명이 줄에 들어온다.

슬라브코는 줄에 서기 전에 핫도그 가판대에 다녀왔다. 그래서 미르코보다 정확히 $K$분 늦게 줄에 들어왔다.

두 사람이 서 있는 칸이 여덟 방향(위, 아래, 왼쪽, 오른쪽, 그리고 네 대각선) 가운데 하나로 맞닿아 있으면 둘은 수다를 떨 수 있다. 두 사람이 줄에서 기다리는 동안 수다를 떠는 시간은 몇 분인가?

위 배치에서 슬라브코가 미르코보다 2분 늦게 줄에 들어오면, 기다리는 동안 모두 3분을 수다에 쓴다.

• 미르코가 6번 칸, 슬라브코가 4번 칸에 있는 1분
• 미르코가 7번 칸, 슬라브코가 5번 칸에 있는 1분
• 미르코가 11번 칸, 슬라브코가 9번 칸에 있는 1분

첫째 줄에 대기줄의 길이 $L$ ($2 \le L \le 250$)과 대기줄의 배치를 나타내는 길이 $L - 1$의 대문자 문자열이 공백으로 구분되어 주어진다. 이 문자열은 줄에서 기다리는 손님이 1번 칸부터 차례로 지나가는 경로를 나타낸다. 문자는 'L', 'R', 'U', 'D' 네 가지이고, 각각 현재 칸의 왼쪽, 오른쪽, 위, 아래 칸으로 옮겨 간다는 뜻이다.

둘째 줄에 슬라브코가 미르코보다 몇 분 늦게 줄에 들어왔는지를 나타내는 자연수 $K$ ($1 \le K < L$)가 주어진다.

첫째 줄의 문자열은 항상 올바른 대기줄 배치를 나타낸다. 즉, 대기줄은 자기 자신과 겹치지 않는다.

미르코와 슬라브코가 수다를 떨 수 있을 만큼 가까이 있는 시간을 분 단위로 출력한다.