Keyboarding timer 4s memory 64MB

아래 그림과 같은 가상 키보드와 조정 버튼을 생각해보자.

왼쪽 그림은 가상키보드이고 오른쪽 그림은 조정버튼이다. 

조정버튼의 방향키를 이용하여 원하는 문자로 이동한 뒤 SEL 버튼을 눌러 원하는 문자를 선택한다. 

원하는 문자를 모두 선택하였다면 마지막으로 Enter키로 이동한 후 SEL 버튼을 눌러야 타이핑이 완료된다.

초기에 커서는 맨 위, 가장 왼쪽 키에 위치하며 상하좌우에 현재위치와 다른 키가 배치된 경우에는 방향키를 이용하여 다른 키로 이동할 수 있다. 

같은 키인 경우 같은 키 너머에 다른 키가 존재하면 그 다른 키로 이동할 수 있다(아래 입력 예 3을 참조).

아래 그림은 입력 예1을 그린 것이다. 

그림에서 붉은색 화살표는 이동한 것을 나타내며, ●은 SEL키를 누른 것을 의미한다. 

아래와 같은 키보드 배치라면 CONTEST를 타이핑하기 위해서 조정버튼을 30번 누르면 되는데 이는 최소의 회수로 누른 것이다.

입력 예3을 예로 들어 좀 더 살펴보자. 입력 정보가 아래와 같이 주어지면

2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ

자판의 모습과 이동 경로를 그려보면 아래 그림과 같을 것이다. (입력값중 '*'은 Enter키를 의미한다.)

처음에 커서는 A키에 있으므로 SEL 버튼을 눌러 선택한다.

아래 버튼을 눌러 X키로 이동한다.

X키에서 오른쪽으로 이동하면 커서는 B아래 Enter키에 위치한다.

B아래 Enter키에서 오른쪽 버튼을 누르면 Y로 이동된다.

Y에서 왼쪽 버튼를 누르면 Z아래 Enter키로 이동된다.

Z아래 Enter키에서 위쪽 버튼을 누르면 Z키로 이동된다. … 이러한 방식으로 이동하여 19번 조정버튼을 누르면 AZAZ를 타이핑할 수 있다. 키보드 배치정보와 입력하고자 하는 문자열을 입력받는다. 

문자열을 타이핑하는데 조정키의 누르는 횟수를 최소로 할 때 누른 횟수를 출력하는 프로그램을 작성하시오.