Potyczki Algorytmiczne już wystartowały! Niestety, Bajtazar nie może zaniedbywać swojej pracy, a jego obowiązki magicznie nie znikają na czas potyczkowego tygodnia. Dzień Bajtazara możemy przedstawić jako $n$ segmentów, każdy trwający jedną bajtogodzinę. Obowiązki podczas każdego z tych segmentów należą do jednej z trzech kategorii:

1. spotkanie w biurze,
2. zdalne spotkanie,
3. brak obowiązków.

W ciągu dnia Bajtazar może być w domu, w biurze lub w drodze między nimi. Bajtazar zaczyna i kończy swój dzień w domu. Może pojechać do biura co najwyżej raz, o ile zdąży wrócić do domu przed upływem $n$-tej bajtogodziny. Przejazdy z domu do biura i z biura do domu trwają dokładnie po $t$ bajtogodzin. W zależności od swojej lokalizacji Bajtazar może podejmować różne działania:

• W domu: Bajtazar oczywiście nie może uczestniczyć w spotkaniu w biurze, może (ale nie musi) uczestniczyć w zdalnym spotkaniu albo może rozwiązywać zadania z rund zdalnych Potyczek Algorytmicznych (ale nie może rozwiązywać zadań, uczestnicząc w spotkaniu).
• W drodze: Bajtazar nie może uczestniczyć w żadnym spotkaniu, ani nie może rozwiązywać zadań – musi się skupić na prowadzeniu samochodu (nie stać go na szofera).
• W biurze: Bajtazar może uczestniczyć w spotkaniu dowolnego typu, a poza spotkaniami musi pracować – nie może wtedy rozwiązywać zadań.

Twoim zadaniem jest zaplanować dzień Bajtazara tak, aby zmaksymalizować liczbę bajtogodzin, podczas których będzie rozwiązywał zadania. Jednakże, jeśli Bajtazar opuści więcej niż $k$ spotkań może zostać zwolniony z pracy. Wtedy jego start w przyszłorocznej edycji, jak wiele innych życiowych spraw, stanąłby pod znakiem zapytania – nie chcemy tego.

Bajtazar jest bardzo dobrze zorganizowany, więc w każdym z segmentów skupia się na dokładnie jednej czynności, w szczególności trasy pomiędzy domem i pracą zajmują mu dokładnie po $t$ całych kolejnych segmentów.

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

В первой строке содержатся три целых числа $n$, $k$ и $t$ ($3 \le n \le 8000$, $0 \le k \le n$, $1 \le t < \frac{n}{2}$), обозначающие соответственно: количество сегментов, количество встреч, которые Бальтазар может пропустить, и время в пути в одну сторону между домом Бальтазара и офисом (в байточасах).

Во второй строке находится слово длины $n$, состоящее из символов 1, 2 или 3, обозначающих тип обязанностей Бальтазара в течение последовательных сегментов дня. Символы соответствуют номерам категорий, приведенным выше в тексте.

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

Выведите одно целое число, обозначающее количество байточасов, которые Бальтазар может потратить на решение задач, не пропустив более $k$ встреч. Если же невозможно пропустить не более $k$ встреч, следует вывести $-1$.

Примеры

Пример 1

10 1 2
3233313132

3

Пример 2

7 0 2
3313233

0

Пример 3

6 5 1
231323

6

Пример 4

4 1 1
1331

-1

Примечание

Пояснение к примерам: В первом примере в одном из оптимальных решений Бальтазар проводит последовательные сегменты дня следующим образом: 1. Решение задач 2. Удаленная встреча из дома 3. Решение задач 4. Дорога на работу 5. Дорога на работу 6. Встреча в офисе 7. Дорога домой 8. Дорога домой (пропускает одну встречу) 9. Решение задач 10. Удаленная встреча из дома

В этом плане Бальтазар пропускает ровно одну встречу и решает задачи в течение 3 байточасов.

Во втором примере единственный план, при котором Бальтазар не теряет работу, выглядит следующим образом: 1. Дорога на работу 2. Дорога на работу 3. Встреча в офисе 4. Работа в офисе 5. Удаленная встреча из офиса 6. Дорога домой 7. Дорога домой

В третьем примере Бальтазар может провести весь день дома, решая задачи и пропуская все удаленные встречи.

В четвертом примере Бальтазар не в состоянии участвовать во встречах в офисе, поскольку не успевает доехать до них или вернуться домой.