题目描述

题目译自 PA 2025 Runda 1 Praca

Potyczki Algorytmiczne 开赛啦！可惜，Bajtazar 不能扔下工作不管，他的职责不会在比赛周神奇消失。他的每天可以分为 $n$ 个时间段，每段持续一字节小时。每个时间段的职责属于以下三类之一：

1. 办公室会议；
2. 远程会议；
3. 无职责。

一天中，Bajtazar 可能在家、在办公室，或在两地途中。他每天从家里开始，也必须回到家里。他最多只能去一次办公室，且需在第 $n$ 个字节小时前赶回家。往返家与办公室的路程各需 $t$ 个字节小时。根据所在位置，他能做的事如下：

• 家里：不能参加办公室会议，可以选择参加远程会议（但非必须），也可以解 PA 的远程题目（但不能边开会边解题）。
• 路上：不能参加任何会议，也不能解题，必须专心开车（他请不起司机）。
• 办公室：可以参加任何类型会议，非会议时间必须工作，不能解题。

你的任务是帮 Bajtazar 规划一天，最大化他解题的字节小时数。但如果他缺席超过 $k$ 次会议，可能会丢掉工作，那样明年参赛和其他生活大事都会泡汤——我们可不想这样。Bajtazar 很有条理，每个时间段只专注一件事，尤其是往返路程恰好占用连续 $t$ 个完整时间段。

输入格式

输入的第一行包含三个整数 $n, k, t$ $(3 \leq n \leq 8000, 0 \leq k \leq n, 1 \leq t < \frac{n}{2})$，分别表示时间段总数、可缺席会议次数上限、单程通勤时间（单位：字节小时）。

第二行是一个长度为 $n$ 的字符串，由 1、2 或 3 组成，表示一天中各时间段的职责类型，对应上述三类。

输出格式

输出一个整数，表示 Bajtazar 在不超过 $k$ 次缺席的情况下，能用于解题的最大字节小时数。若无法做到缺席不超过 $k$ 次，则输出 -1。

10 1 2
3233313132

3

在第一个样例中，Byteasar 的一个最优计划如下：

1. 解题；
2. 在家里远程会议；
3. 解题；
4. 去办公室；
5. 去办公室；
6. 办公室会议；
7. 回家
8. 回家（缺席一次会议）；
9. 解题；
10. 在家里远程会议。

Byteasar 缺席 $1$ 次，解题 $3$ 小时。

7 0 2
3313233

0

在第二个样例中，Byteasar 为保工作，唯一计划是：

1. 去办公室；
2. 去办公室；
3. 办公室会议；
4. 工作；
5. 在办公室远程会议；
6. 回家；
7. 回家。

6 5 1
231323

6

在第三个样例中，Byteasar 可以整天在家，忽略所有远程会议。

4 1 1
1331

-1

在第四个样例中，Byteasar 无法准时参加办公室会议又赶回家。