URI Online Judge | 2795


By Luciano Ribeiro BR Brazil

Timelimit: 1

Given a string of characters \(S\), you were given the challenge of turning it into a palindrome. A palindrome is a text that is exactly the same if read from right to left as well as from left to right. For example, racecar e radar are palindromes.

To transform a text into a palindrome, you can choose a position \(i\) in the text and replace the letter in this position with any other letter. This operation has a cost that is the distance between the letter of the alphabet that was before and the one that you chose. Note that the alphabet is circular, so you can substitute a for z with cost \(1\). You can apply this same operation as many times as you want, each time adding the cost as described.

Because sometimes you need many modifications to transform an entire string into a palindrome, you have been allowed to divide the original string into up to \(K\) contiguous segments, so that after each modification, each of those segments is a palindrome. This division has no cost. The total cost of the transformation you made will be the sum of the costs of the operations performed on each segment. What is the lowest possible cost for turning all segments into palindromes?


The entry begins with a line containing two integers \(N\) and \(K\), separated by space. The second line contains a string \(S\) with \(N\) characters formed only by lower case letters of the alphabet, from a to z.

\(1 \leq K \leq N \leq 400\)


Write in the output a line containing an integer: the least cost to transform \(S\) into a palindrome, given you can partition it into up to \(K\) contiguous segments.

Input Sample Output Sample

4 1


4 1


4 2


4 3