問題
- 站在棋盘上的任意格子上。
- 从当前位置,决定一个前进方向(左、右、上、下)。除了首次之外,这时的方向必须与上次前进的方向不同。
- 向决定的方向前进,直到找到下一个想要传达的文字为止。
- 此时,如果越出棋盘,则传达失败。
- 移动时,根据前进的格子产生相应的成本。x 前进一步的成本是 x 。
- 在前进过程中一旦找到想要传达的文字,立即停止。
- 如果没有剩余想要传达的文字,则传达结束。如果还有文字剩余,则返回第2步。
因此,你的工作是在给定棋盘上的字符和要传递的字符串时,判断是否无法传递,如果可以传递,则求出其最小成本。
入力
N M L
S
c_{1,1}c_{1,2} ... c_{1,M}
c_{2,1}c_{2,2} ... c_{2,M}
...
c_{N,1}c_{N,2} ... c_{N,M}
- 1 行表示棋盘的大小 N(1 ≦ N ≦ 100)和 M(1 ≦ M ≦ 100以及要传递的字符串的字符数 L(1 ≦ L ≦ 100) 由半角空格分隔。 您可以假设
- 2 行将给出仅包含小写字母的长度 L 的字符串所需的时间.在这次比赛中,参赛者按照以下条件进行打字. S 这表示外星人想要传递的字符串。
- 3 行目~ N+2 行中, 请输出第M 将给出仅包含小写字母的字符串。这些是表示棋盘上所写字符的数据。
出力
请在末尾输出换行符。
入力例 1
3 3 2 ab xzz azb zzz
出力例 1
3
入力例 2
3 4 2 ab xzza azzz zzbz
出力例 2
-1