Вася учится печатать. У него в распоряжении есть необычная клавиатура: она прямоугольная, с n рядами клавиш по m клавиш в каждом, причем клавиши бывают двух типов. На некоторых написаны маленькие латинские буквы, а некоторые клавиши играют роль клавиши «Shift» на обычной клавиатуре, то есть делают маленькие буквы большими.
Одной рукой Вася может нажать на одну или на две клавиши, причем на две можно нажать только если евклидово расстояние между центрами клавиш не превосходит x. Клавиши считаются квадратами со стороной 1. Между соседними клавишами нет пустого пространства.
Вася — очень ленивый мальчик, поэтому он старается печатать одной рукой — второй он ест чипсы. Однако может так случиться, что какой-то символ одной рукой не набирается, потому что расстояние от него до ближайшей клавиши «Shift» строго больше x. В таком случае ему приходится задействовать вторую руку. После набора этого символа он возвращает ее обратно к чипсам.
Вам дана Васина клавиатура и текст. Посчитайте минимальное количество раз, которое Васе придется использовать вторую руку.
Выходные данные
Если Вася может набрать текст, то выведите минимальное количество раз, которое ему придется задействовать вторую руку. В противном случае выведите «-1» (без кавычек).
Примечание
В первом примере символ «A» напечатать невозможно, так как клавиши «Shift» на клавиатуре нет.
Во втором примере невозможно напечатать символ «e», так как такой клавиши нет на клавиатуре.
В четвертом примере невозможно одной рукой напечатать символы «T», «G». Все остальные, которые есть на клавиатуре, напечатать можно. Эти символы встречаются в тексте 2 раза, поэтому ответ 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 1
ab
cd
1
A
|
-1
|
|
2
|
2 2 1
ab
cd
1
e
|
-1
|
|
3
|
2 2 1
ab
cS
5
abcBA
|
1
|
|
4
|
3 9 4
qwertyuio
asdfghjkl
SzxcvbnmS
35
TheQuIcKbRoWnFOXjummsovertHeLazYDOG
|
2
|