화상 키보드

화상 키보드(OSK)로 문자열을 입력하려고 한다. 화살표 4개와 OK, 다섯 개의 버튼이 달린 리모컨(그림 B-1)으로 OSK를 조작한다. 주어진 OSK로 주어진 문자열을 입력하는 데 필요한 최소 버튼 입력 횟수를 구하라.

그림 B-1 리모컨

그림 B-2 화상 키보드의 예

입력할 문자	강조 칸의 이동	버튼 입력
I		→,→,→,→,→,→,→,→,OK (9회)
C		←,←,←,←,←,←,OK (7회)
P		↓,→,→,→,→,OK (6회)
C		↑,←,←,←,←,OK (6회)

그림 B-3 그림 B-2의 OSK로 “ICPC”를 입력하는 최소 절차

OSK는 격자로 배치된 칸들로 이루어지며, 각 칸에는 문자가 하나 들어 있거나 아무것도 들어 있지 않다. 서로 다른 두 칸에 같은 문자가 들어 있는 경우는 없다.

OSK의 칸 하나가 강조되어 있고, OK 버튼을 누르면 그 칸에 문자가 들어 있을 경우 그 문자를 입력한다.

처음에는 왼쪽 위 칸이 강조되어 있다. 화살표 버튼을 하나 누르면 강조된 칸이 화살표 방향으로 인접한 칸 중 하나로 바뀐다. 강조된 칸이 OSK의 가장자리에 있을 때 가장자리 밖으로 나가는 방향의 화살표 버튼을 누르면 아무 변화도 일어나지 않는다.

예를 들어 그림 B-2와 같이 배치된 OSK에서 문자열 “ICPC”는 그림 B-3과 같이 28회의 버튼 입력으로 입력할 수 있으며, 이것이 최소 횟수이다.

OSK의 칸에 들어가는 문자는 소문자(‘a’, ‘b’, ..., ‘z’), 대문자(‘A’, ‘B’, ..., ‘Z’), 숫자(‘0’, ‘1’, ..., ‘9’), 쉼표(‘,’), 하이픈(‘-’), 마침표(‘.’), 슬래시(‘/’), 콜론(‘:’), 세미콜론(‘;’), 골뱅이 기호(‘@’) 중 하나이다.

입력은 최대 100개의 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식이다.

h w
r1
...
rh
s

첫 줄의 두 정수 h와 w는 각각 OSK의 높이와 너비이다. 두 값은 공백으로 구분되며 1 ≤ h ≤ 50, 1 ≤ w ≤ 50을 만족한다.

다음 h개의 줄은 각각 OSK의 한 행을 나타낸다. i번째 행 ri는 길이 w의 문자열이다. 문자열의 문자는 왼쪽에서 오른쪽으로 OSK의 i번째 행 칸에 들어 있는 문자, 또는 빈 칸을 나타내는 밑줄(‘_’)에 대응한다.

주어진 OSK는 위에 적힌 조건을 만족한다.

그다음 줄은 입력할 문자열 s이다. s의 길이는 1 이상 1000 이하이다. s의 모든 문자는 주어진 OSK에 나타난다. s에는 밑줄이 들어 있지 않다.

입력의 끝은 두 개의 0이 들어 있는 줄로 표시된다.

각 데이터셋에 대해 주어진 OSK로 주어진 문자열을 입력하는 데 필요한 최소 버튼 입력 횟수를 한 줄에 하나씩 출력한다.