Введем \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}.