Controlling set of strings#4660
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 given a non-empty string s. Find the multiset of non-empty substrings of s that has the maximum possible sum of lengths, contains exactly strings, and such that each suffix of s is controlled by at least one string from this set.
Note that the substrings in the resulting set do not have to be unique.
The first line contains the string s (1 \leq |s| \leq 10^5) — the given string. The second line contains an integer (1 \leq k \leq \min(100, |s|)) — the required number of substrings in the set.
The string consists only of lowercase Latin letters.
Output a single integer — the maximum possible sum of the lengths of the strings in the optimal set. If it is not possible to form such a set, output -1.
Example 1