P11914 [PA 2025] 上班 / Praca

PA 2025 R1B.

一天被分为 $n$ 段时间。每段时间可能会有以下三种事情： 1. 举行了一场线下会议； 2. 举行了一场线上会议； 3. 空闲。 每段时间内，Bajtazar 所在的地点可能有三种： - 在家： - 在家里无法参加线下会议（被迫翘掉会议）。 - 在家里**可以**参加线上会议（也可以选择翘掉会议做题）。 - 在家里可以做题。 - 在公司： - 在公司**必须**参加线下会议。 - 在公司**必须**参加线上会议。 - 在公司**无法**做题。 - 在通勤： - 通勤时无法参加线下会议（被迫翘掉会议）。 - 通勤时无法参加线上会议（被迫翘掉会议）。 - 通勤时无法做题。 一天开始时（第 $1$ 段时间初），Bajtazar 在家里。一天结束时（第 $n$ 段时间末），Bajtazar 必须回到家中。 Bajtazar 可以选择去办公室**至多一次**。从家到办公室、从办公室回家都要通勤。 通勤会消耗 $t$ 段时间，即如果选择在第 $i$ 段时间初开始通勤，在第 $(i+t-1)$ 段时间末会结束通勤。 Bajtazar 想打一辈子算法竞赛，所以他想抽出尽可能多的时间做题。但是他最多能翘掉 $k$ 场会议，请帮他算出至多能用多少个时间段来做题。

第一行，三个整数 $n,k,t$。 第二行，一个长度为 $n$ 的字符串 $s$。$s_i\in \{1,2,3\}$，表示第 $i$ 段时间的类型（1：线下会议；2：线上会议；3：空闲）。

如果不可能翘掉 $\le k$ 场会议，输出一行一个 $-1$。 否则输出一行一个非负整数表示答案。

### 样例解释 样例 $1$ 解释：一个最优解如下。 1. 解题（在家） 2. 线上会议（在家） 3. 解题（在家） 4. 通勤（去办公室） 5. 通勤（去办公室） 6. 线下会议（在办公室） 7. 通勤（回家） 8. 通勤（回家，被迫翘掉一场会议） 9. 解题（在家） 10. 线上会议（在家） - 样例 $2$ 解释：唯一一个解如下。 1. 通勤（去办公室） 2. 通勤（去办公室） 3. 线下会议（在办公室） 4. 空闲（在办公室） 5. 线上会议（在办公室） 6. 通勤（回家） 7. 通勤（回家） - 样例 $3$ 解释：一整天都待在家里，翘掉所有会议。 - 样例 $4$ 解释：第一场会议和最后一场会议都无法参加。 ### 数据范围 - $3\le n\le 8\, 000$； - $0\le k\le n$； - $1\le t\lt n/2$。