Пятница — любимый день недели Поликарпа. Не потому, что за пятницей идут выходные, а потому что в пятницу по расписанию 2 урока информатики, 2 математики и 2 литературы. Поликарп, конечно, подготовился ко всем урокам, чего не скажешь о его хорошем друге Иннокентие. Иннокентий не успел подготовиться к уроку литературы, поскольку весь вечер четверга провел за игрой в любимую игру Fur2. Чтобы не получить двойку Иннокентий решил выполнить домашнее задание по литературе и прочитать книгу «Буря и затишье» во время уроков информатики и математики (с этими предметами у Иннокентия никогда не было проблем). Увидев это, учитель информатики Валерий Петрович решил дать Иннокентию задание (чтобы тот не скучал и не занимался посторонними вещами).

Валерий Петрович сказал, что палиндромом называется строка, одинаково читающаяся как слева направо, так и справа налево. А конкатенацией строк a, b называется строка ab, получающаяся последовательным приписыванием строки b к строке a. Это все Иннокентий, конечно, знал, но задание было намного сложнее, чем он мог себе представить. Валерий Петрович попросил изменить в книге «Буря и затишье» наименьшее число символов, чтобы текст книги оказался конкатенацией не более k палиндромов. С такой задачей Иннокентий не в силах справиться, поэтому попросил вас помочь ему.