Flower_Rainbow_and

题号：NC311640
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ Flower 准备用一排气球来装饰房间。他有 $n$ 个气球排成一行，气球的颜色有三种，分别为红色（使用字母 $\texttt{`r'}$ 表示）、黄色（ $\texttt{`y'}$ ）和白色（ $\texttt{`w'}$ ）。不同颜色的气球能带来不同的愉悦度：红色为 $2$ ，黄色为 $1$ ，白色为 $0$ 。

$\hspace{15pt}$ 为了达到最好的装饰效果，Flower 决定从中选取一个非空的连续子区间。选定区间后，他会邀请 Rainbow 对该区间施展一次魔法。Rainbow 的魔法包含以下两个步骤：
$\hspace{23pt}\bullet\,$ 第一步，「颜色反转」：选择是否将区间内所有红色气球全变成黄色、黄色气球全变成红色（同时进行）。
$\hspace{23pt}\bullet\,$ 第二步，「点缀」：他可以将区间内至多 $m$ 个白色气球染成红色。
$\hspace{15pt}$ Flower 希望经过 Rainbow 的魔法处理后，该区间的气球愉悦度之和至少为 $k$ 。

$\hspace{15pt}$ 为了节省空间，Flower 希望他选取的这个区间长度尽可能短。请你帮助他判断这样的区间是否存在，如果存在，计算满足条件的最小区间长度。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入三个整数 ，表示气球数量、「点缀」最多可处理的气球数量、期望的愉悦度之和；
第二行输入一个长度为 、仅由字符 , ,  组成的字符串 ，表示每个气球的颜色。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行。若存在合法的区间，输出最小区间长度；否则输出 。

示例1

输入

复制

6
1 1 2
r
1 1 2
y
1 1 2
w
3 0 5
ryy
6 1 2
yyyywy
5 5 11
wwwww

输出

复制

说明

以下样例解释给出最优策略，但是不一定是唯一最优策略。下标从  开始。

对于第一组样例，选取  区间，「颜色反转」不互换，「点缀」染色  个，区间内的气球颜色变为 （即不进行任何操作）；
对于第二组样例，选取  区间，「颜色反转」互换，「点缀」染色  个，区间内的气球颜色变为 ；
对于第三组样例，选取  区间，「颜色反转」不互换，「点缀」染色  个，区间内的气球颜色变为 ；
对于第四组样例，选取  区间，「颜色反转」互换，「点缀」染色  个，区间内的气球颜色变为 ；
对于第五组样例，选取  区间，「颜色反转」不互换，「点缀」染色  个，区间内的气球颜色变为 。