eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Робот

Робот

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Робот двигается по полю, состоящему из n клеток, расположенных подряд. На каждой клетке находится кубик определённого цвета.

В начале движения робот находится в первой клетке поля и не держит ни одного кубика. Находясь в клетке, робот может выполнить не более одного раза каждую из следующих операций: (1) положить кубик того же цвета, что лежит в текущей клетке; (2) поднять с клетки тот кубик, который находился в ней сначала. После этого робот перемещается в следующую клетку или останавливается, если текущая клетка является последней на поле.

Одновременно робот может держать не более чем k кубиков. В момент остановки робот не должен держать ни одного кубика.

Напишите программу, которая по информации о цвете кубиков и ограничении на количество кубиков, которое может держать робот, определяет общее максимальное количество кубиков, которые робот может перенести с места на место, двигаясь по полю.

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

Первая строка содержит строку длины n (1 n 1000). Строка состоит из маленьких букв латинского алфавита. Каждая буква соответствует клетке поля и определяет цвет кубика, который находится в этой клетке. Вторая строка содержит ограничения на количество кубиков, которые может одновременно держать робот k (1 k 25).

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

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

Пример

Входные данные #1
rgbbggrmcm
2
Выходные данные #1
4
Автор Шамиль Ягияев
Источник 2004 XVII Всеукраинская олимпиада по информатике, Харьков, Март 28 - Апрель 3, тур 2