Преодолев лестницу, Даша оказалась на занятиях. Чтобы начать заниматься, ей необходимо ввести пароль. Пароль — это строка длины n, удовлетворяющая следующим требованиям:
- В строке присутствует как минимум одна цифра,
- В строке присутствует как минимум одна строчная (маленькая) буква латинского алфавита,
- В строке присутствует как минимум один из трёх перечисленных символов — '#', '*', '&'.
Учитывая, что это занятия по программированию, просто так записать пароль не получится.
Для каждого символа пароля закреплена некоторая строка длины m, на каждой из этих n строк стоит указатель на некоторый символ в этой строке. Символ номер i на экране это символ, на который указывает указатель в i-ой строке. Изначально все указатели стоят на символе с индексом 1 (все позиции в этой задаче нумеруются с единицы).
За одну операцию Даша может передвинуть указатель любой одной строки на один символ влево или вправо. Строки цикличны, то есть при сдвиге указателя, который стоит на символе с индексом 1, влево, он перемещается на символ с индексом m, а при сдвиге вправо с позиции m он переместится на позицию 1.
Вам необходимо определить минимальное количество операций, необходимых для того, чтобы строка, отображаемая на экране, стала паролем.
Выходные данные
Выведите одно целое число — минимальное количество операций, необходимых для того, чтобы строка, отображаемая на экране, стала паролем.
Примечание
В первом примере для получения оптимального ответа нужно передвинуть указатель третьего символа на один влево.
Во втором примере одной из возможных последовательностей действий будет:
- сдвинуть указатель второго символа вправо.
- сдвинуть указатель третьего символа дважды вправо.
