时空限制

1S/512M

题目描述

注意：本题并不是摩卡串（string）。

给定一个长度为 $n$ 的 $01$ 序列。你可以对该序列执行至多 $k$ 次区间翻转操作。

在每次操作中，你可以选择任意区间 $[l, r]$（$1 \le l \le r \le n$），并将该区间内所有的字符进行翻转（即将所有的 0 变为 1，所有的 1 变为 0）。

我们称一个 $01$ 序列为非摩卡串，当且仅当该序列中任意相邻的两个字符均不相同（即序列呈现 010101... 或 101010... 的交替形态）。

请计算在执行至多 $k$ 次操作后，原序列中能够构成的最长非摩卡子串的长度。

格式

输入格式

第一行包含两个整数 $n, k$，分别表示 $01$ 序列的长度和最多可以进行的区间翻转次数。

第二行包含一个长度为 $n$ 的字符串，仅由字符 0 和 1 组成，表示初始的 $01$ 序列。

输出格式

输出共一行，包含一个整数，表示在最优策略下，执行至多 $k$ 次操作后能够得到的非摩卡串的最大长度。

样例

样例输入 #1

7 1
1000101

样例输出 #1

7

样例解释 #1

对 $[3,3]$ 执行翻转操作，可以得到序列为 1010101，故答案为 $7$。

样例输入 #2

10 2
1011100111

样例输出 #2

9

样例解释 #2

1. 第一步对 $[4,8]$ 进行翻转操作，得到序列为 1010011011。
2. 第二步对 $[5,6]$ 进行翻转操作，得到序列为 1010101011。

可以发现 $[1,9]$ 为最长的非摩卡串，故答案为 $9$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$k\le$	子任务依赖
$1$	$50$	$2000$		无
$2$	$50$	$2\times 10^5$		$1$

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le k \le n$，且输入的字符串仅包含字符 0 和 1。