Words

Memory limit: 32 MB

By a word we mean a sequence of capital letters of the English alphabet. The length of a word is the number of letters contained in it. This way, word ABAACBBBA is of length 9. By a block within a word we understand maximal consistent subsequence of the same letters. A word is called -hard, if it contains blocks. Taking into consideration the word , it turns out to be 6-hard, because it consists of the following blocks: A|B|AA|C|BBB|A.

If two given words are of the same length, it is possible to check how different they are. Two words of the length are -different, if for exactly positions (), 'th letter of the first word is different from 'th letter of the second word. Checking two words and AAAABBBBB, it turns out that they are 3-different.

For a given word , we want to find not too different word , so that it is not too complicated. Your task is to define, how simple can be.

Task

Write a program which:

• reads the numbers and a word of length ;
• determines the minimal value of , so that there exists a -hard word , which is at most -different from (which is, there is no , so that and are -different);
• writes the answer to the standard output.

Input

In the first line of the standard input there are two integers separated with a single space (, ). They represent adequately: the length of the word and the allowed level of difference. In the second line there are exactly capital letters forming the word .

Output

One integer is to be written to the standard output - .

Example

For the input data:

9 3
ABAACBBBA

the correct result is:

2

Task author: Tomasz Idziaszek.