Problem1031--「一本通 1.4 练习 2」Keyboarding

1031: 「一本通 1.4 练习 2」Keyboarding

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

出自 World Final 2015 F. Keyboarding

给定一个 rrrccc 列的在电视上的“虚拟键盘”,通过「上,下,左,右,选择」共 555 个控制键,你可以移动电视屏幕上的光标来打印文本。一开始,光标在键盘的左上角,每次按方向键,光标总是跳到下一个在该方向上与当前位置不同的字符,若不存在则不移动。每次按选择键,则将光标所在位置的字符打印出来。
现在求打印给定文本(要在结尾打印换行符)的最少按键次数。


Input

第一行输入 r,cr,cr,c
接下来给出一个 r×cr\times cr×c 的键盘,包括大写字母,数字,横线以及星号(星号代表Enter换行)。
最后一行是要打印的文本串 SSSSSS 的长度不超过 100001000010000


Output

输出打印文本(包括结尾换行符)的最少按键次数。保证一定有解。


Sample Input

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

Sample Output

19

HINT

对于 100%100\%100% 的数据,1≤r,c≤50,1\le r,c\le 50,1r,c50, SSS 的长度不超过 100001000010000


Source/Category


Submit Status