C. Даша и пароль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Преодолев лестницу, Даша оказалась на занятиях. Чтобы начать заниматься, ей необходимо ввести пароль. Пароль — это строка длины n, удовлетворяющая следующим требованиям:

  • В строке присутствует как минимум одна цифра,
  • В строке присутствует как минимум одна строчная (маленькая) буква латинского алфавита,
  • В строке присутствует как минимум один из трёх перечисленных символов — '#', '*', '&'.

Учитывая, что это занятия по программированию, просто так записать пароль не получится.

Для каждого символа пароля закреплена некоторая строка длины m, на каждой из этих n строк стоит указатель на некоторый символ в этой строке. Символ номер i на экране это символ, на который указывает указатель в i-ой строке. Изначально все указатели стоят на символе с индексом 1 (все позиции в этой задаче нумеруются с единицы).

За одну операцию Даша может передвинуть указатель любой одной строки на один символ влево или вправо. Строки цикличны, то есть при сдвиге указателя, который стоит на символе с индексом 1, влево, он перемещается на символ с индексом m, а при сдвиге вправо с позиции m он переместится на позицию 1.

Вам необходимо определить минимальное количество операций, необходимых для того, чтобы строка, отображаемая на экране, стала паролем.

Входные данные

В первой строке находятся два целых числа n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 50) — длина пароля и длина строк закрепленных за символами пароля.

В каждой из следующих n строк находится строка, закрепленная за i-м символом строки-пароля, длины m, состоящая из цифр, строчных латинских букв и символов '#', '*', '&'.

Входные данные таковы, что всегда можно получить строку-пароль.

Выходные данные

Выведите одно целое число — минимальное количество операций, необходимых для того, чтобы строка, отображаемая на экране, стала паролем.

Примеры
Входные данные
3 4
1**2
a3*0
c4**
Выходные данные
1
Входные данные
5 5
#*&#*
*a1c&
&q2w*
#a3c#
*&#*&
Выходные данные
3
Примечание

В первом примере для получения оптимального ответа нужно передвинуть указатель третьего символа на один влево.

Во втором примере одной из возможных последовательностей действий будет:

  • сдвинуть указатель второго символа вправо.
  • сдвинуть указатель третьего символа дважды вправо.