Vasya 学习打字。他有一个不寻常的键盘可供使用:它是矩形的,有 n 行按键,每行包含 m 个按键。此外,钥匙有两种类型。有些键上有小写拉丁字母,有些键的作用类似于标准键盘上的“Shift”键,也就是说,它们将小写字母变成大写。
Vasya 可以用一只手按一个或两个键。然而,如果按键中心之间的欧氏距离不超过x,他只能按下两个按键。键被视为边长等于 1 的正方形。相邻键之间没有空格。
Vasya 是一个非常懒的男孩,这就是为什么他尝试用一只手打字,另一只手吃薯条。然而,某些符号可能无法仅用一只手输入,因为它与最近的“Shift”键之间的距离严格大于x。在这种情况下,他将不得不使用另一只手。输入符号后,瓦西亚将另一只手放回筹码上。
您将获得 Vasya 的键盘和文本。计算 Vasya 必须使用另一只手的最少次数。
输入
第一行包含三个整数 n、m、x (1 ≤ n, m ≤ 30, 1 ≤ x ≤ 50)。
接下来的 n 行包含所有键盘按键的描述。每行包含恰好 m 个键的描述,不带空格。字母键标有相应的小写字母。 “Shift”键标有“S”符号。
然后遵循文本 q 的长度 (1 ≤ q ≤ 5·105)。最后一行包含文本 T,它由 q 符号组成,q 符号是大写和小写拉丁字母。
输出
如果 Vasya 可以输入文本,则打印出他必须使用另一只手的最少次数。否则,打印“-1”(不带引号)。
示例
输入 #1
2 2 1 ab cd 1 A
输出 #1
-1
输入 #2
2 2 1 ab cd 1 e
输出 #2
-1
输入 #3
2 2 1 ab cS 5 abcBA
输出 #3
1
输入#4
3 9 4 qwertyuio asdfghjkl SzxcvbnmS 35 TheQuIcKbRoWnFOXjummsovertHeLazYDOG
输出#4
2
注意
在第一个示例中,无法打印符号“A”,因为键盘上没有“Shift”键。
在第二个示例中,无法打印符号“e”,因为键盘上没有这样的键。
在第四个示例中,无法用一只手打印符号“T”、“G”。可以打印键盘上的其他字母。这些符号在文本中出现了两次,因此答案是 2。