给你一根绳子 $$$n$$$ 个单位长,每个单位都涂成红色或黑色。绳子可以表示为由字符组成的长度为 $$$n$$$ 的字符串 R (红色)和 B (黑色)。您还获得两个整数 $$$m$$$ 和 $$$k$$$。
您可以执行以下操作 最多 $$$m$$$ 次(可能为零次):
- 选择长度恰好为 $$$k$$$ 的绳子的任何连续子字符串$$$^{\text{*}}$$$。
- 翻转子串中每个单元的颜色:each R 变为 B,以及每个 B 变为 R.
例如,考虑绳索 RRRRBRRR $$$k = 4$$$。如果您选择第 $$$3$$$ 到第 $$$6$$$ 个字符 (RRRRBRRR),那么翻转后,绳子就变成 RRBBRBRR.
定义 颜色段数 作为绳索可以分成的连续段的最小数量,以便每个段由单一颜色的单元组成。例如,绳子 RRBRRRBB 有 $$$4$$$ 颜色段: RR, B, RRR,和 BB.
您的任务是确定执行后颜色段的最大可能数量 最多 $$$m$$$ 操作。
$$$^{\text{*}}$$$ 字符串 $$$t$$$ 是字符串 $$$s$$$ 的子字符串,如果 $$$t$$$ 可以通过从 $$$s$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
输入
第一行包含三个整数$$$n$$$、$$$m$$$和$$$k$$$,分别代表绳子的长度、允许的最大操作数以及每个操作的翻转窗口的长度。
第二行包含长度为 $$$n$$$ 的字符串,仅由字符组成 R 和 B,代表绳索的初始内容。
- $$$1 \le n \le 3000$$$
- $$$0 \le m \le 3000$$$
- $$$1 \le k \le n$$$
输出
单行输出一个整数,表示最多执行$$$m$$$操作后可能出现的最大色段数。
示例
输入复制
5 4 3RRBRR
输出复制
5
输入复制
10 3 3RRRRBBRRRB
输出复制
8
输入复制
7 4 7RRBRBBR
输出复制
5