题目描述

你有一个长方形的键盘，共 $n$ 行，每行 $n$ 个键。每个键可以打出小写字母，在按下 Shift 键时也可以打出大写字母。键盘上每个键是一个边长为 $1$ 的正方形，相邻的键之间没有空隙。

你想用一只手吃辣条，另一只手编程，所以你得尝试只用一只手打字。但是当打字时按的键离 Shift 键太远（欧几里得距离大于 $x$）时，你就不得不用到另一只手。 请计算出使用另一只手的最小次数。

输入格式

第一行包含一个整数 $n,m,x$（$1\le n,m\le 30,1\le x\le 50$）。

接下来的 $n$ 行包含键盘排列的描述，每行有 $m$ 个字符，字符间没有空格，$\texttt S$ 代表 Shift 键。

接下来的一个整数代表文本长度 $q$（$1\le q\le 5\times 10^5$）。接下来有 $q$ 个字符代表文本，文本中只有大写和小写字母。

输出格式

如果你能打出这一篇文本，那么输出另一只手的最小使用次数。如果无法全部打出（比如文本中有大写字母但没有 Shift 键，或键盘上没有要打的键）时，则输出 $-1$。

2 2 1
ab
cd
1
A

-1

2 2 1
ab
cd
1
e

-1

2 2 1
ab
cS
5
abcBA

1

3 9 4
qwertyuio
asdfghjkl
SzxcvbnmS
35
TheQuIcKbRoWnFOXjummsovertHeLazYDOG

2