The last Ballade...
Time limit: 1000 ms
Memory limit: 512 MB
_The stage gradually darkens. The spotlight now shines on only one person. Kaori – the girl with the violin who revived Kousei's world – can no longer stand by his side. She is fighting for every second of life. The performance they once promised now has only Kousei performing a solo on the vast, silent, and heavy stage._ _Chopin’s Ballade No. 1 echoes, each piano key like a heartbeat – gentle yet painful. Within that sound, Kaori’s image appears – as if her soul glides through the notes, stirring the layers of emotion, making the music both enchanting and weighty._ Kousei’s piece has a total of $n$ notes, each note carrying an emotional tone represented by a number $0$ or $1$ – corresponding to a flat or sharp note, respectively. A sequence of music is considered emotionally rich if it can be divided into one or two groups of adjacent notes with the same emotion (for example: $00111$, $1111$, or $11000$ – but not $0101$ or $0100$). The sequence of music may be a subset of notes that are not necessarily contiguous. When Kaori appears in Kousei’s mind, she changes a part of the music – at most once – by inverting the emotion of a contiguous segment of exactly $k$ notes. In that case, what is the length of the longest emotionally rich sequence that can be formed? ### Input - The first line contains two positive integers $n,k.$ - The second line contains a string $S$ of length $n$ describing the notes of the music. ### Output - Print the answer to the problem. ### Constraints - $1 \le k \le n \le 200000$. ### Example Input: ``` 6 3 110001 ``` Output: ``` 6 ``` Input: ``` 7 2 1010010 ``` Output: ``` 6 ```
Topic
Others