eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Виборча система

Виборча система

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Студенти Байтляндского університету для занять використовують автоматичну систему реєстрації. Реєстрація відкрита певний період часу. При цьому кожний момент часу має характеристику, яка описується додатним числом. Входити в систему можна не більше k разів, кожний вхід може тривати не більше d одиниць часу. Періоди знаходження в системі не повинні перетинатися.

Є рядок, i - ий символ якого описує характеристику в i - ий момент часу. Характеристика задається літерами від 'a' до 'z', що позначають відповідно числа від 1 до 26. Необхідно розробити стратегію входу до системи, при якій сума характеристик на періоди часу знаходження в системі найбільша.

Вхідні дані

Перший рядок кожного тесту містить значення d та k\:(1 \le d, k \le 1000). Другий містить набір з небільш ніж 1000 літер 'a' — 'z'.

Вихідні дані

Для кожного тесту в окремому рядку виведіть найбільшу можливу суму характеристик.

Приклад

Вхідні дані #1
4 1
acacca
2 2
cabcca
2 18
yptcsevnuzlsrfjxurpslztlinhddelpitmvaezowjcfjjfgmfq
Вихідні дані #1
10
10
598