← 返回题目列表

Codeforces · 88/B

B. 键盘

中文机器翻译题面 查看原题

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。