题目描述

小智正在参加一场数字闯关赛，关卡给出了一个由 n 个字符组成的序列，每个字符只能是 N 或 F。闯关要求是：小智最多可以对序列中的字符进行 k 次修改操作（每次操作可将一个 N 改为 F，或一个 F 改为 N），修改后，需要使序列的 “最大不平衡度” 最小化。 这里的 “最大不平衡度” 定义为：序列中最长的连续子段内 N 的个数或F 的个数。小智需要找到一种修改方式，使得这个 “最大不平衡度” 尽可能小，计算出这个最小的最大不平衡度对应的数值。

输入格式

1. 第一行输入两个整数 n 和 k，分别表示序列的长度和允许修改的次数；​
2. 第二行输入 n 个字符，每个字符是 N 或 F，代表闯关序列（字符之间用空格分隔）。

输出格式

输出一个整数，表示符合的最小的最大不平衡度对应的数值。

输入输出样例 #1

输入 #1

8 1
NNNFFNNN

输出 #1

3

说明/提示

$30\%$ 的数据：$1\le k \le n\le20$；

$50\%$ 的数据：$1\le k \le n\le300$；

另有 $15\%$ 的数据：$1\le k \le n\le 10^5$，字符串为全 N 或全 F；

$100\%$ 的数据：$1\le k \le n\le 10^5$。