Controlling set of rows
Let's define the concept of a control relation for a set of strings. A string a controls another string b if either a is a prefix of b, or b is a prefix of a.
You are provided with a non-empty string s. Your task is to determine the multiset of non-empty substrings of s that maximizes the sum of their lengths. This multiset should contain exactly k strings, and each suffix of s must be controlled by at least one string from this set.
Note that the substrings in the resulting set do not have to be unique.
Input
The first line contains the string s (1 ≤ |s| ≤ 10^5) — the given string. The second line contains an integer k (1 ≤ k ≤ min(100, |s|)) — the required number of substrings in the set.
The string consists solely of lowercase Latin letters.
Output
Output a single integer — the sum of the lengths of the strings in the optimal set. If such a set cannot be formed, output -1.