J. Journey To Stringland
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the mystical kingdom of Stringland, where characters and sequences hold the secrets to ancient magic, there exists a revered challenge that tests the wisdom and skill of the realm's scribes. This challenge, known as "The Quest for the Palindromic Subsequence," involves transforming ordinary sequences of letters into powerful palindromic symbols.

You, a scribe of Stringland, are given a sequence of characters $$$S$$$ and must undertake a quest to create a palindromic subsequence of length $$$K$$$. Palindromic sequences are believed to hold magical properties as they read the same forward and backward. To aid in your quest, you are allowed to change any character in $$$S$$$ to any other character. The fewer changes you make, the stronger the resulting magic.

Determine the minimum number of character changes needed for $$$S$$$ to contain at least one palindromic subsequence of length $$$K$$$.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq K \leq N \leq 500$$$), representing the length of the string $$$S$$$ and the size of the palindromic subsequence. The second line contains the string $$$S$$$, composed of lowercase English letters.

Output

Output one line with an integer, the minimum number of character changes needed for $$$S$$$ to contain at least one palindromic subsequence of length $$$K$$$.

Examples
Input
3 3
abc
Output
1
Input
10 4
abcdcaefgj
Output
0
Input
5 2
abcde
Output
1
Note

A subsequence of a given sequence is a sequence that can be derived from the original sequence by deleting some or none of the elements without changing the order of the remaining elements. For example, if the original sequence is ( A = {a, b, c, d, e} ), then ( {a, b, d} ) and ( {c, e} ) are subsequences of ( A ), but ( {b, a} ) is not a subsequence because it changes the order of the elements.