003 - スクリーンキーボード

リモコンでスクリーンキーボードを操作して文字列を入力したい. リモコンには 4 方向の矢印と OK のボタンがついている（図 B-1）． 与えられた文字列を与えられたスクリーンキーボードで入力するのに必要な最小ボタン押下回数を求めよ.

入力する文字	強調表示の動き	ボタン操作
I		→,→,→,→,→,→,→,→,OK（9回）
C		←,←,←,←,←,←,OK（7回）
P		↓,→,→,→,→,OK（6回）
C		↑,←,←,←,←,OK（6回）

スクリーンキーボードは格子状に並んだセルからなり, 各セルには文字がひとつあるか空である. 複数のセルが同じ文字を含むことはない．

スクリーンキーボードのセルのひとつは強調表示されていて, 空でないセルが強調表示されているときにリモコンの OK ボタンを押すと, そのセルの文字が入力される.

最初はスクリーンキーボードの左上隅のセルが強調されている． 矢印ボタンのひとつを押すと, 強調セルはその矢印の示す方向の隣のセルに移る. 強調セルがスクリーンキーボードの端にあるときには, スクリーンキーボードから出るような方向の矢印ボタンを押しても何も起きない.

例えば図 B-2 に示すスクリーンキーボード上で文字列 “ICPC” を入力するには, 図 B-3 に示す手順でボタンを 28 回押せばよい. これが最小ボタン押下回数である.

スクリーンキーボードのセルに入っている文字は, 英小文字 (‘a’, ‘b’, ..., ‘z’)， 英大文字 (‘A’, ‘B’, ..., ‘Z’)， 数字 (‘0’, ‘1’, ..., ‘9’)， コンマ (‘,’)， ハイフン (‘-’)， ピリオド (‘.’)， スラッシュ (‘/’)， コロン (‘:’)， セミコロン (‘;’)， アットマーク (‘@’) のいずれかである．

入力は次の形式の最大 100 個のデータセットからなる．

h w
r₁
...
r_h
s

データセットの最初の行のふたつの整数 h と w は，それぞれスクリーンキーボードの高さと幅である．これらは空白で区切られており, 1 ≤ h ≤ 50 と 1 ≤ w ≤ 50 を満たす.

続く h 行に，スクリーンキーボードの各行が与えられる． i 番目の行 r_i はスクリーンキーボードの i 行目を表している． r_i は長さ w の文字列であり，スクリーンキーボードの i 行目の文字が左から順に並んだものである． ただし，スクリーンキーボード上の空のセルは，アンダースコア (‘_’) で表現されている．

スクリーンキーボードは上述の条件を満たす．

続く行の s は，長さ 1 以上 1000 以下の，入力したい文字列である． s に含まれる文字は，必ず与えられたスクリーンキーボード上に存在する． s はアンダースコアを含まないことに注意．

入力の終わりはゼロふたつからなる行で表される．

各データセットについて，与えられた文字列を与えられたスクリーンキーボードで入力するのに必要な最小ボタン押下回数を表す整数ひとつをもつ行を出力せよ．

3 9
ABCDEFGHI
JKLMNOPQR
STUVWXYZ_
ICPC
5 11
___________
____A______
________M__
___________
_C_________
ACM
4 21
1_2_3_4_5_6_7_8_9_0_-
QqWwEeRrTtYyUuIiOoPp@
AaSsDdFfGgHhJjKkLl;_:
ZzXxCcVvBbNnMm,_._/__
ICPC2019,AsiaYokohamaRegional,QualificationRound
0 0

28
23
493