Potyczki Algorytmiczne 已经开始了！不幸的是，Bajtazar 不能忽视他的工作，他的职责也不会在比赛周期间神奇地消失。我们可以将 Bajtazar 的一天看作 $n$ 个时间段，每个时间段持续一小时（bajtogodzina）。每个时间段的职责属于以下三类之一： 1. 办公室会议， 2. 远程会议， 3. 无职责。

在一天中，Bajtazar 可能在家里、办公室或往返于两者之间的路上。Bajtazar 在家里开始和结束他的一天。他最多可以去一次办公室，前提是他能在第 $n$ 小时结束前回到家。从家到办公室以及从办公室到家的路程各需要恰好 $t$ 小时。根据他所在的位置，Bajtazar 可以采取不同的行动： 在家：Bajtazar 当然不能参加办公室会议，他可以（但不必须）参加远程会议，或者他可以解决 Potyczki Algorytmiczne 的远程比赛题目（但不能在参加会议的同时解决题目）。 在路上：Bajtazar 不能参加任何会议，也不能解决题目——他必须专注于开车（他雇不起司机）。 * 在办公室：Bajtazar 可以参加任何类型的会议，而在会议之外的时间他必须工作——此时他不能解决题目。

你的任务是规划 Bajtazar 的一天，以最大化他解决题目的总小时数。然而，如果 Bajtazar 错过的会议超过 $k$ 场，他可能会被解雇。那样的话，他参加明年比赛的机会，就像许多其他生活琐事一样，将变得悬而未决——我们不希望这样。

Bajtazar 非常有条理，因此在每个时间段内他只专注于做一件事，特别是往返于家和办公室的行程需要他占用恰好 $t$ 个连续的时间段。

输入格式

第一行包含三个整数 $n, k$ 和 $t$ ($3 \le n \le 8000, 0 \le k \le n, 1 \le t < \frac{n}{2}$)，分别表示时间段总数、Bajtazar 可以错过的会议数量，以及往返于家和办公室单程所需的时间（以小时为单位）。

第二行包含一个长度为 $n$ 的字符串，由字符 1、2 或 3 组成，表示 Bajtazar 在一天中各个时间段的职责类型。字符对应于文中提到的类别编号。

输出格式

输出一个整数，表示在不超过 $k$ 次缺席的情况下，Bajtazar 可以用来解决题目的总小时数。如果无法在不超过 $k$ 次缺席的情况下完成任务，则输出 $-1$。

样例

输入 1

10 1 2
3233313132

输出 1

3

输入 2

7 0 2
3313233

输出 2

0

输入 3

6 5 1
231323

输出 3

6

输入 4

4 1 1
1331

输出 4

-1

说明

样例解释：在第一个样例中，一种最优方案是 Bajtazar 按以下方式度过一天： 1. 解决题目 2. 在家参加远程会议 3. 解决题目 4. 去办公室的路上 5. 去办公室的路上 6. 办公室会议 7. 回家的路上 8. 回家的路上（错过一场会议） 9. 解决题目 10. 在家参加远程会议

在这个计划中，Bajtazar 恰好错过了一场会议，并解决了 3 小时的题目。

在第二个样例中，Bajtazar 不会丢掉工作的唯一计划如下： 1. 去办公室的路上 2. 去办公室的路上 3. 办公室会议 4. 在办公室工作 5. 在办公室参加远程会议 6. 回家的路上 7. 回家的路上

在第三个样例中，Bajtazar 可以整天待在家里，解决题目并跳过所有远程会议。

在第四个样例中，Bajtazar 无法参加办公室会议，因为他无法及时赶到或无法及时从办公室回到家。