Алгоритмические состязания уже начались! К сожалению, Бальтазар не может забросить свою работу, а его обязанности магическим образом не исчезают на время соревновательной недели. День Бальтазара можно представить как $n$ сегментов, каждый из которых длится один байточас. Обязанности во время каждого из этих сегментов относятся к одной из трех категорий:

1. встреча в офисе,
2. удаленная встреча,
3. отсутствие обязанностей.

В течение дня Бальтазар может находиться дома, в офисе или в пути между ними. Бальтазар начинает и заканчивает свой день дома. Он может поехать в офис не более одного раза, при условии, что успеет вернуться домой до истечения $n$-го байточаса. Поездки из дома в офис и из офиса домой занимают ровно по $t$ байточасов каждая. В зависимости от своего местоположения Бальтазар может выполнять различные действия:

• Дома: Бальтазар, очевидно, не может участвовать во встрече в офисе, может (но не обязан) участвовать в удаленной встрече или может решать задачи из удаленных раундов Алгоритмических состязаний (но не может решать задачи, участвуя во встрече).
• В пути: Бальтазар не может участвовать ни в каких встречах и не может решать задачи — он должен сосредоточиться на вождении автомобиля (он не может позволить себе водителя).
• В офисе: Бальтазар может участвовать во встрече любого типа, а в остальное время обязан работать — в такие моменты он не может решать задачи.

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

Бальтазар очень организован, поэтому в каждом из сегментов он сосредоточен ровно на одном действии; в частности, поездки между домом и работой занимают у него ровно по $t$ последовательных сегментов.

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

В первой строке содержатся три целых числа $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. Дорога домой

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

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