Вы играете в новую часть знаменитого файтинга: Kortal Mombat XII. Вы хотите совершить brutality на персонаже вашего противника.
Вы играете в игру на консоли нового поколения, поэтому на вашем геймпаде есть \(26\) кнопок. На каждой кнопке записана строчная буква латинского алфавита от 'a' до 'z'. Все буквы на кнопках попарно различны.
Вам задана последовательность ударов, \(i\)-й удар наносит \(a_i\) единиц урона персонажу противника. Чтобы совершить \(i\)-й удар, вам необходимо нажать кнопку \(s_i\) на вашем геймпаде. Удары пронумерованы от \(1\) до \(n\).
Вы знаете, что если вы нажмете какую-то кнопку больше, чем \(k\) раз подряд, то она сломается. Вы очень дорожите своим геймпадом и не хотите ломать никакую из его кнопок.
Чтобы совершить brutality, вам необходимо нанести некоторые удары из заданной последовательности. Вы можете пропустить любой из них, но менять изначальный порядок ударов вам запрещено. Суммарный нанесенный урон равен сумме \(a_i\) по всем \(i\) среди ударов, которые не были пропущены.
Заметьте, что если вы пропускаете удар, тогда счетчик последовательных нажатий кнопки не будет сброшен.
Ваша задача — пропустить сколько-то ударов таким образом, чтобы нанести максимально возможный урон персонажу противника и не сломать ни одну из кнопок вашего геймпада.
Выходные данные
Выведите одно целое число \(dmg\) — максимально возможный урон персонажу противника, который вы можете нанести без поломки кнопок вашего геймпада.
Примечание
В первом тестовом примере вы можете выбрать удары с номерами \([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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 3
1 5 16 18 7 2 10
baaaaca
|
54
|
|
2
|
5 5
2 4 1 3 1000
aaaaa
|
1010
|
|
3
|
5 4
2 4 1 3 1000
aaaaa
|
1009
|
|
4
|
8 1
10 15 2 1 4 8 15 16
qqwweerr
|
41
|
|
5
|
6 3
14 18 9 19 2 15
cccccc
|
52
|
|
6
|
2 1
10 10
qq
|
10
|