Elective System#1559
Students of Byteland University use an automatic registration system for classes. Registration is open for a certain period, and each time unit is assigned a characteristic represented by a positive integer. You may log in to the system at most times, and each login can last for at most time units. The login periods must not overlap.
You are given a string where the -th character represents the characteristic at the -th time unit. The characteristic is given as a letter from '' to '', which correspond to numbers from to , respectively. Find a login strategy such that the sum of the characteristics over the periods when you are logged in is maximized.
The first line of each test case contains the values of and (1 \le d,\ k \le 1000). The second line contains a string of at most letters from '' to ''.
For each test case, output on a separate line the largest possible sum of characteristics.
Example 1