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