Having inadvertently annoyed the deity in charge of the sky, Ed was exiled to another world as punishment. Compared to his original world, the language of this other world also uses $26$ lowercase English letters to convey information; however, the expression of information does not rely on sentence breaks. If a sentence contains too much information, it becomes unacceptable. Specifically, for two strings $s_1, s_2$, let $w(s_1, s_2)$ be the number of distinct strings that are common substrings of both $s_1$ and $s_2$. For a sentence $t$ of length $m$, let $t[l, r]$ denote the substring of $t$ from the $l$-th character to the $r$-th character (1-indexed). The information content of $t$ is defined as: $$ val(t) = \sum_{i=1}^{m-1} w^2(t[1,i],t[i+1,m]) $$

Having finally adapted to life in this other world, Ed used his past experience in learning algorithms to get a job that only exists in this world: an article segmenter. His daily task is to split articles into individual sentences. To maintain aesthetic appeal, the number of sentences in an article must be exactly $k$. Ed's goal is to minimize the maximum information content among all sentences in the article, thereby enhancing its readability.

To realize his plan to escape this world, Ed needs to search for time fragments scattered across various locations. However, to continue surviving in this world, he cannot lose his job, so he has asked you to help him pass his daily task checks. Specifically, for each article, you need to answer: under the condition that the maximum information content among the sentences is minimized, what is this maximum information content?

Input

The first line contains two integers $n$ and $k$, representing the length of the article and the number of sentences to be formed.

The second line contains an article $t$ of length $n$ consisting only of lowercase English letters.

Output

Output a single integer representing the maximum information content among the sentences after the optimal segmentation.

Examples

Input 1

10 3
ababababab

Output 1

11

Input 2

15 2
abcabcddcbacbad

Output 2

57

Subtasks

For all data, $1 \leq n \leq 5 \times 10^4, 1 \leq k \leq n$. It is guaranteed that the answer does not exceed $10^{18}$.

• Subtask 1 (10 pts): $n \leq 10$
• Subtask 2 (10 pts): $n \leq 50$
• Subtask 3 (20 pts): $n \leq 200$
• Subtask 4 (20 pts): $n \leq 1000$
• Subtask 5 (40 pts): No additional constraints.