Виборча система
Виборча система
Студенти Байтляндского університету для занять використовують автоматичну систему реєстрації. Реєстрація відкрита певний період часу. При цьому кожний момент часу має характеристику, яка описується додатним числом. Входити в систему можна не більше k разів, кожний вхід може тривати не більше d одиниць часу. Періоди знаходження в системі не повинні перетинатися.
Є рядок, i - ий символ якого описує характеристику в i - ий момент часу. Характеристика задається літерами від 'a' до 'z', що позначають відповідно числа від 1 до 26. Необхідно розробити стратегію входу до системи, при якій сума характеристик на періоди часу знаходження в системі найбільша.
Вхідні дані
Перший рядок кожного тесту містить значення d та k\:(1 \le d, k \le 1000). Другий містить набір з небільш ніж 1000 літер 'a' — 'z'.
Вихідні дані
Для кожного тесту в окремому рядку виведіть найбільшу можливу суму характеристик.
Приклад
4 1 acacca 2 2 cabcca 2 18 yptcsevnuzlsrfjxurpslztlinhddelpitmvaezowjcfjjfgmfq
10 10 598