C. Brutality
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в новую часть знаменитого файтинга: Kortal Mombat XII. Вы хотите совершить brutality на персонаже вашего противника.

Вы играете в игру на консоли нового поколения, поэтому на вашем геймпаде есть $$$26$$$ кнопок. На каждой кнопке записана строчная буква латинского алфавита от 'a' до 'z'. Все буквы на кнопках попарно различны.

Вам задана последовательность ударов, $$$i$$$-й удар наносит $$$a_i$$$ единиц урона персонажу противника. Чтобы совершить $$$i$$$-й удар, вам необходимо нажать кнопку $$$s_i$$$ на вашем геймпаде. Удары пронумерованы от $$$1$$$ до $$$n$$$.

Вы знаете, что если вы нажмете какую-то кнопку больше, чем $$$k$$$ раз подряд, то она сломается. Вы очень дорожите своим геймпадом и не хотите ломать никакую из его кнопок.

Чтобы совершить brutality, вам необходимо нанести некоторые удары из заданной последовательности. Вы можете пропустить любой из них, но менять изначальный порядок ударов вам запрещено. Суммарный нанесенный урон равен сумме $$$a_i$$$ по всем $$$i$$$ среди ударов, которые не были пропущены.

Заметьте, что если вы пропускаете удар, тогда счетчик последовательных нажатий кнопки не будет сброшен.

Ваша задача — пропустить сколько-то ударов таким образом, чтобы нанести максимально возможный урон персонажу противника и не сломать ни одну из кнопок вашего геймпада.

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — количество ударов и максимальное нажатий на одну и ту же кнопку подряд.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ равно урону $$$i$$$-го удара.

Третья строка входных данных содержит строку $$$s$$$, состоящую ровно из $$$n$$$ строчных букв латинского алфавита — последовательность ударов (каждый символ — это буква на кнопке, на которую вам необходимо нажать, чтобы нанести соответствующий удар).

Выходные данные

Выведите одно целое число $$$dmg$$$ — максимально возможный урон персонажу противника, который вы можете нанести без поломки кнопок вашего геймпада.

Примеры
Входные данные
7 3
1 5 16 18 7 2 10
baaaaca
Выходные данные
54
Входные данные
5 5
2 4 1 3 1000
aaaaa
Выходные данные
1010
Входные данные
5 4
2 4 1 3 1000
aaaaa
Выходные данные
1009
Входные данные
8 1
10 15 2 1 4 8 15 16
qqwweerr
Выходные данные
41
Входные данные
6 3
14 18 9 19 2 15
cccccc
Выходные данные
52
Входные данные
2 1
10 10
qq
Выходные данные
10
Примечание

В первом тестовом примере вы можете выбрать удары с номерами $$$[1, 3, 4, 5, 6, 7]$$$ с суммарным уроном $$$1 + 16 + 18 + 7 + 2 + 10 = 54$$$.

Во втором тестовом примере вы можете выбрать все удары, таким образом максимальный урон равен $$$2 + 4 + 1 + 3 + 1000 = 1010$$$.

В третьем тестовом примере вы можете выбрать все удары кроме третьего, таким образом максимальный урон равен $$$2 + 4 + 3 + 1000 = 1009$$$.

В четвертом тестовом примере вы можете выбрать удары с номерами $$$[2, 3, 6, 8]$$$. Только таким способом вы можете достичь максимального суммарного урона $$$15 + 2 + 8 + 16 = 41$$$.

В пятом тестовом примере вы можете выбрать только удары с номерами $$$[2, 4, 6]$$$ с максимальным суммарным уроном $$$18 + 19 + 15 = 52$$$.

В шестом тестовом примере вы можете выбрать либо первый удар, либо второй удар (это не имеет значения) с суммарным уроном $$$10$$$.