题目背景

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$。

否则输出一行一个非负整数表示答案。

10 1 2
3233313132

3

7 0 2
3313233

0

6 5 1
231323

6

4 1 1
1331

-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$。