Контролююча множина рядків#4660
Введемо відношення контролю на множині рядків. Рядок a контролює рядок b, якщо або a є префіксом b, або b є префіксом a.
Вам задано непорожній рядок s. Знайдіть найбільшу за сумою довжин мультимножину непорожніх підрядків рядка s, яка складається з рівно рядків, таку що кожен суфікс рядка s контролюється хоча б одним рядком з цієї множини.
Усі підрядки знайденої множини не обов'язково повинні бути різними.
У першому рядку записано рядок s (1 \leq |s| \leq 10^5) — заданий рядок. У другому рядку записано ціле число (1 \leq k \leq \min(100, |s|)) — потрібна кількість підрядків у множині.
Заданий рядок складається лише з рядкових латинських літер.
Виведіть єдине ціле число — суму довжин рядків оптимальної множини. Якщо описаної множини не існує, виведіть -1.
Приклад 1