G. Streak Manipulation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This semester, Mr. Ham spent a lot of time in training for ICPC. He has $$$n$$$ classes this semester, and he only attended some of them. He uses a binary string $$$s_{1..n}$$$ to represent which classes he attended. If the $$$i$$$-th character of the string is $$$\texttt{1}$$$, he attended the $$$i$$$-th class. Otherwise, he didn't attend the $$$i$$$-th class.

If Mr. Ham attended $$$k$$$ consecutive classes, he would get a streak of length $$$k$$$. Formally, if $$$1\leq i\leq j\leq n$$$ satisfies the following conditions, we say that Mr. Ham has a streak of length $$$j-i+1$$$:

  • $$$s_i=s_{i+1}=\cdots=s_j=\texttt{1}$$$;
  • $$$i=1$$$ or $$$s_{i-1}=\texttt{0}$$$;
  • $$$j=n$$$ or $$$s_{j+1}=\texttt{0}$$$.

For example, if $$$s=\texttt{101101}$$$, Mr. Ham has one streak of length $$$2$$$ and two streaks of length $$$1$$$.

Mr. Ham found that he was absent from too many classes. So he stole the attendance record and wants to change it (It's not allowed, so please don't do that). Given $$$m$$$ and $$$k$$$, he can change at most $$$m$$$ records from $$$\texttt{0}$$$ to $$$\texttt{1}$$$. He wants to know the maximum length of the $$$k$$$-th longest streak he can get.

If there are less than $$$k$$$ streaks, we define the length of $$$k$$$-th longest streak as $$$-1$$$.

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1\leq m\leq n\leq 2\times 10^5$$$, $$$1\leq k\leq \min(n, 5)$$$).

The second line contains a string $$$s$$$ of length $$$n$$$. It is guaranteed that $$$\forall 1\leq i\leq n, s_i \in \{\texttt{0},\texttt{1}\}$$$.

Output

Output the maximum length of the $$$k$$$-th longest streak Mr. Ham can get by changing at most $$$m$$$ records from $$$\texttt{0}$$$ to $$$\texttt{1}$$$.

Examples
Input
8 3 2
10110110
Output
3
Input
12 3 3
100100010011
Output
2
Input
4 4 4
0000
Output
-1