July 12 - ADA Training

Elective System

The students at Byteland Institute of Technology are registering electronically for classes. Registration is open for a predetermined number of time units, and each time unit is assigned a positive number called the goodness. Higher goodness values mean that the network is more likely to be available and responsive during those time units. You may log in at most k times during the registration period. Each login may last a maximum of d time units, and logins must not overlap with each other.

You are given a string values. The i-th character of this string represents the goodness value of the ith time unit. The goodness values are given as characters 'a' to 'z', which represent values 1 to 26, respectively. Choose a strategy that maximizes the total goodness of the time units during which you are logged in, and find this total goodness value.


The first line of each test case containsthe values of d and k (1d, k1000). The second line contains the string values that contains no more than 1000 letters 'a' - 'z'.


For each test case print in a separate line the maximal possible total goodness value.

Time limit 1 second
Memory limit 64 MiB
Input example #1
4 1
2 2
2 18
Output example #1