403186: GYM101063 D Interstellar Love

"Sit back, children, for I will tell you about the first love story between Mars and Earth."

Everyone knows the story of Gabriela, the lady that managed to send thousands of love messages through the first mission's main science channel to her beloved back on Mars. What few people know is that, although she was an artist, she used a very unique algorithm to do that.

Back in the first days of GEMA, communicating between Mars and Earth was kept only for scientific research, for budget reasons. The mission was using a very simple way of verifying if a message was related to science. They asked for a number, K, to be attached to the message. This number was the answer to an algorithmic puzzle. The puzzle went like this, as written in the missions's log:

The number K should be calculated as follows.

First, two strings S and T must be built.

To build S, consider a sequence of strings composed by the first M suffixes of the message after having ordered all of them lexicographically. Then, choose a subsequence of this sequence, S will be the concatenation of the strings in the chosen subsequence.

To build T, consider a sequence of strings composed by the first M suffixes of the message, after having them sorted by length in descending order. Then, choose a subsequence of this sequence, T will be the concatenation of the strings in the chosen subsequence.

The number K is the length of the longest S and T that can be built, such that S = T.

Did this guarantee that only science people would get their message through? Probably not, as history shows, but it was enough for higher management. Your job here is to be as awesome as Gabriela was in the good old days and write an algorithm to calculate K for a given message.

The input contains two lines, the first line contains two integers N, M (1 ≤ N ≤ 5 × 10³, 1 ≤ M ≤ min{N, 100}) which are the length of the message and the number of suffixes to consider, when building S and T (as explained above). The second line contains the message A, containing only lower case english letters.

Print K.

3 2
aaa

3

6 5
ooouch

15

A subsequence is a sequence with some elements removed without changing their order.

In the first sample, the message is AAA.

S : A | AA

T : AAA