Minimum Replacements for Consecutive Crayons

You are given a row of n crayons, each having a color represented by a lowercase letter. Your task is to perform a set of replacements on these crayons in order to achieve the following conditions in the final configuration:

• There is exactly one contiguous block of crayons of some color c whose length is exactly k.
• For every color that appears in the final configuration, all of its occurrences must appear in one contiguous block.

You may replace any crayon’s color with any other color. Note that you can also choose a color which is not initially present in the row. If you choose such a color, since no crayon of that color exists in the initial configuration, you will effectively create a block of length k by performing k replacements.

The cost of a solution is measured by the total number of replacements performed. Find the minimum number of replacements needed to meet the above requirements.

Hint: One strategy is to choose a color and look at the maximum length of a contiguous block of that color in the original string. Then, the number of replacements needed if using that color is equal to the absolute difference between k and this maximum run length. Also consider the possibility of choosing a new color (which would cost k replacements).

In mathematical terms, if for a chosen color c the maximum consecutive occurrence length is \(L\), then the cost for c is:

[ \text{cost}(c)=|k-L| \quad \text{,} ]

and the answer is the minimum among all choices (including the option to create a new color, with cost k).

inputFormat

The input is given via stdin and consists of:

1. A line with two integers n and k, where n is the number of crayons and k is the required length of the contiguous block.
2. A line containing a string s of length n representing the initial colors of the crayons.

outputFormat

Output via stdout a single integer: the minimum number of replacements required to achieve the desired configuration.

## sample

6 3
abacbd

2