Контролирующее множество строк
Введем отношение контроля на множестве строк. Строка a контролирует строку b, если либо a является префиксом b, либо b является префиксом a.
Вам задана непустая строка s. Найдите наибольшее по сумме длин мульти-множество непустых подстрок строки s, состоящее из ровно k строк, такое что каждый суффикс строки s контролируется хотя бы одной строкой из этого множества.
Все подстроки найденного множества не обязательно должны быть различны.
Входные данные
В первой строке записана строка s (1 ≤ |s| ≤ 10^5) — заданная строка. Во второй строке записано целое число k(1 ≤ k ≤ min(100, |s|)) — требуемое количество подстрок в множестве.
Заданная строка состоит только из строчных латинских букв.
Выходные данные
Выведите единственное целое число — сумма длин строк оптимального множества. Если описанного множества не существует выведите -1.