가상 키보드 입력

그림 1의 왼쪽은 4x7 크기의 가상 키보드다. 사용자는 가상 키보드의 키를 직접 누르지 못하고, 그림 오른쪽에 있는 하드웨어 버튼 5개만 쓴다. 커서는 가상 키보드의 왼쪽 맨 위 키에서 시작하고, 화살표 버튼 네 개가 커서를 움직인다. 화살표를 한 번 누르면 커서는 그 방향으로 다른 문자가 나올 때까지 이동한다. 그 방향에 다른 문자가 없으면 커서는 움직이지 않는다. 원하는 키 위에서 선택(SEL) 버튼을 누르면 그 문자가 텍스트 끝에 붙는다. 이렇게 텍스트의 문자를 차례로 입력하고, 입력을 끝내려면 Enter 키를 찾아 선택 버튼을 눌러야 한다.

그림 1. 가상 키보드와 하드웨어 버튼의 예

그림 1은 이 키보드로 CONTEST를 입력하는 방법을 보여준다. 화살표는 화살표 버튼을 누르는 동안 커서가 지나간 경로이고, 점은 선택 버튼을 누를 키다. CONTEST를 입력하는 데 키 입력 30번이 든다.

가상 키보드 배치와 텍스트가 주어진다. 그 텍스트를 입력하는 데 필요한 최소 키 입력 횟수를 구하라.

첫째 줄에 가상 키보드 격자의 행 수와 열 수 $r$과 $c$가 주어진다 ($1 \le r, c \le 50$). 다음 $r$개 줄에 키보드가 주어지며, 각 줄은 문자 $c$개로 이루어진다. 문자는 대문자, 숫자, 대시(-), 별표(*) 중 하나이고 별표는 Enter 키를 뜻한다. 같은 문자에 해당하는 키는 하나뿐이다. 각 키는 격자 칸 하나 이상으로 이루어지고 항상 연결된 영역을 이룬다. 마지막 줄에 입력할 텍스트가 주어진다. 텍스트는 문자 10,000개 이하로 이루어진 문자열이고, 별표를 포함하지 않으며, 빈 문자열이 아니다. 주어진 텍스트는 주어진 가상 키보드로 입력할 수 있다.

마지막 Enter까지 포함해서 텍스트 전체를 입력하는 데 필요한 최소 키 입력 횟수를 출력한다.