Mumble, along with his Adele penguin friends, Ramon, Raul and Nestor, were joking around one day when Raul suddenly burst out laughing.
“Hey, Ramon, I can turn your name into a palindrome. Like this. Ramar. Ramar. Rrramarrrrrr.” he chuckled, rolling his r's like only Adele penguins can.
“Oh yeah? Yours is even worse, isn't it? Raar. Raar. Rrrraarrrrrrrr.”
Mumble, being the very very pensive penguin, decided to ignore all that pointless banter and instead concentrate on one of the most important questions in the universe: how many characters does he have to change to make a word a palindrome? Or, even more important, how many characters would he have to change to make a length n word a concatenation of at most k palindromes?
“You two are ridiculous. Maybe all of us are ridiculous. How about Ramonraulnestor? Rar-onrauluarno-r. Look, I did it by changing only 5 characters! Oh no, now I'm ridiculous too. Bwahahahaha!” mused Nestor.
Random interjections by his hyperactive friends are making it really difficult for Mumble to concentrate on the palindrome problem. It's imperative that he solves it as fast as he can, otherwise all his friends and family will run out of fish and starve to death. Help Mumble solve this conundrum. Given a length n string, output the minimum number of characters he would have to change to transform the string into a concatenation of at most k palindromes.
Input
The first line contains n and k.
The second line contains the string in question, containing only lowercase alphabets from a to z.
Output
Output a single integer on a line representing the minimum number of character changes needed to transform the string into a concatenation of k palindromes.
Limits
1 ≤ k ≤ n.
For 25% of the test cases, 1 ≤ n ≤ 10.
For 50% of the test cases, 1 ≤ n ≤ 100.
For 100% of the test cases, 1 ≤ n ≤ 500.
Sample Input 1
5 1
ramon
Sample Output 1
2
Sample Input 2
15 3
ramonraulnestor
Sample Output 2
5