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

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

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

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

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

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

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

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