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

Контролирующее множество строк

Контролирующее множество строк

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

Введем отношение контроля на множестве строк. Строка aконтролирует строку b, если либо a является префиксом b, либо b является префиксом a.

Вам задана непустая строка s. Найдите наибольшее по сумме длин мульти-множество непустых подстрок строки s, состоящее из ровно k строк, такое что каждый суффикс строки s контролируется хотя бы одной строкой из этого множества.

Все подстроки найденного множества не обязательно должны быть различны.

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

В первой строке записана строка s (1|s|10^5) — заданная строка. Во второй строке записано целое число k(1kmin(100, |s|)) — требуемое количество подстрок в множестве.

Заданная строка состоит только из строчных латинских букв.

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

Выведите единственное целое число — сумма длин строк оптимального множества. Если описанного множества не существует выведите -1.

Пример

Входные данные #1
aba
1
Выходные данные #1
-1
Источник Зимняя школа Харьков 2013, День 6 - Г.Агапова и И.Фефера