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