Сегодня в научном лицее Королевства Кремляндия был урок биологии. Темой урока были геномы. Назовем геномом строку «ACTG».
Максиму было очень скучно сидеть на уроке, поэтому учитель придумал для него задание: по заданной строке \(s\), состоящей из заглавных латинских букв и длины как минимум \(4\), необходимо найти минимальное количество операций которое нужно применить, чтобы в ней появился геном как подстрока. За одну операцию можно заменить любую букву в строке \(s\) на следующую или предыдущую в алфавите. Например, для буквы «D» предыдущей будет «C», а следующей — «E». В этой задаче считаем, что для буквы «A» предыдущей будет буква «Z», а следующей — буква «B», а для буквы «Z» предыдущей будет буква «Y», а следующей — буква «A».
Помогите Максиму решить задачу, которую дал ему учитель.
Напомним, что строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Выходные данные
Выведите минимальное количество операций, которые нужно применить к строке \(s\), чтобы в ней появился геном как подстрока.
Примечание
В первом примере следует заменить букву «Z» на «A» за одну операцию, букву «H» — на букву «G» за одну операцию. Получится строка «ACTG», в которой присутствует геном как подстрока.
Во втором примере заменим букву «A» на «C» за две операции, букву «D» — на букву «A» за три операции. Получится строка «ZACTG», в которой есть геном.