F. 키보드 입력

문자 메시지 하나를 입력하는 데 몇 번의 키 입력이 필요할까? 텍스트의 문자 수와 같다고 생각할지 모르지만, 이는 키 입력 한 번이 문자 하나를 만들 때에만 맞는 말이다. 주머니 크기(pock\(et- si\)ze) 기기에서는 텍스트 입력 방법이 제한되는 경우가 많다. 어떤 기기는 알파벳 글자 수보다 훨씬 적은 몇 개의 버튼만 제공한다. 그런 기기에서는 문자 하나를 입력하는 데 여러 번의 입력이 필요할 수 있다. 이런 제한에 대처하는 한 가지 방법이 화면에 표시되는 가상 키보드로, 키에서 키로 커서를 옮겨 문자를 선택할 수 있다. 네 개의 화살표 버튼으로 커서의 이동을 제어하고, 커서가 원하는 키 위에 있을 때 다섯 번째 버튼을 누르면 해당 문자가 선택되어 텍스트 끝에 덧붙는다. 텍스트를 끝내려면 사용자는 Enter 키로 이동해 선택해야 한다. 이렇게 하면 임의의 문자 집합을 제공하면서 하드웨어 버튼 다섯 개만으로 임의 길이의 텍스트를 입력할 수 있다. 이 문제에서는 가상 키보드 배치가 주어지고, 주어진 텍스트를 입력하는 데 필요한 최소 입력 횟수를 구해야 한다. 다섯 개의 하드웨어 버튼 중 어느 것이든 한 번 누르는 것이 입력 한 번이다. 키들은 직사각형 격자에 배열되어 있으며, 각 가상 키는 격자의 연결된 단위 정사각형 한 개 이상을 차지한다. 커서는 키보드의 왼쪽 위 모서리에서 시작해 동서남북 네 방향으로 움직이는데, 항상 그 방향에서 다른 키에 속하는 다음 단위 정사각형으로 건너뛴다. 그런 단위 정사각형이 없으면 커서는 움직이지 않는다. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Enter ↑ ← ↓ → SEL 그림 F.1: 샘플 입력 1. 가상 키보드와 하드웨어 버튼의 예. 샘플 입력 1을 나타낸 그림 F.1은 예시 가상 키보드에서 30번의 입력으로 CONTEST를 입력하는 한 가지 방법을 보여 준다. 빨간 점은 선택 버튼이 눌린 가상 키를 나타낸다.

입력의 첫 줄에는 가상 키보드 격자의 행 수와 열 수인 두 정수 \(r\)과 \(c\) (\(1 \le r\), \(c \le 50\))가 주어진다. 가상 키보드는 다음 \(r\)개의 줄에 지정되며, 각 줄에는 \(c\)개의 문자가 있다. 이 문자들의 가능한 값은 대문자, 숫자, 대시, 그리고 (Enter를 나타내는) 별표이다. 주어진 문자에 대응하는 키는 하나뿐이다. 각 키는 한 개 이상의 격자 정사각형으로 이루어지며, 이들은 항상 연결된 영역을 이룬다. 입력의 마지막 줄에는 입력할 텍스트가 주어진다. 이 텍스트는 별표를 제외한 사용 가능한 문자 최대 10 000개로 이루어진 비어 있지 않은(n\(on-em\)pty) 문자열이다.

마지막의 Enter 키를 포함하여 전체 텍스트를 입력하는 데 필요한 최소 입력 횟수를 출력한다. 텍스트를 입력할 수 있음이 보장된다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2015