Description

From ICPC World Final 2015 F. Keyboarding

Given an $r$-row by $c$-column "virtual keyboard" on a TV screen, you can move the cursor to print text using five control keys: "up, down, left, right, select." Initially, the cursor is at the top-left corner of the keyboard. Each time a direction key is pressed, the cursor jumps to the next character in that direction that is different from the current position (if no such character exists, the cursor does not move). Pressing the select key prints the character at the cursor's current position.
Now, determine the minimum number of key presses required to print the given text (including the newline character at the end).

Input Format

The first line contains $r$ and $c$.
Next, an $r \times c$ keyboard is provided, consisting of uppercase letters, numbers, hyphens, and asterisks (the asterisk represents the Enter newline character).
The last line contains the text string $S$ to be printed, with a length not exceeding $10,000$.

Output Format

Output the minimum number of key presses required to print the text (including the ending newline character). A solution is guaranteed to exist.

Sample 1

1. Press A once
2. Move down (X), right (*), right (Y), left (*), up (Z) — $5$ moves
3. Press Z once
4. Move down (*), left (X), up (A) — $3$ moves
5. Press A once
6. Move from A to Z — $5$ moves
7. Press Z once
8. Move down (*) — $1$ move
9. Press * once

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

19

Sample 2

5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015

160

Sample 3

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

7

Constraints & Notes

For $100\%$ of the data, $1 \le r, c \le 50$, and the length of $S$ does not exceed $10,000$.