Trader Joe Trades

The order of the transactions is fixed; each one has a type A..Z and an integer profit, and any of them can be skipped. In the selected sequence, the same type may not appear more than k times in a row. Maximize the profit; selecting nothing is allowed and gives profit 0. A transaction with negative profit may still be worth taking as a separator, so such transactions cannot simply be dropped.

输入格式

The first line contains n k, the second line is the string formed by the n transaction types, and the third line contains n profits; when n=0 the last two lines are empty. On this site 0≤n≤2000, −10^9≤profit≤10^9, 0≤k≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

5 2
BAAAB
1 4 2 10 3

输出：

18

样例 2

输入：

3 1
ABA
100 -1 100

输出：

199

样例 3

输入：

3 1
ABA
10 -100 10

输出：

10

样例说明

The outputs of the three public examples are 18; 199; and 10, checked by independent enumeration or direct simulation.