Moloco es una empresa de tecnología publicitaria que ayuda a diversas compañías de todo el mundo a mejorar su publicidad en línea. Gracias a la tecnología de Moloco, los usuarios de Internet pueden ver anuncios más relevantes y los anunciantes pueden realizar sus campañas de manera efectiva.
Jongseo ha predicho que un usuario visitará una página web un total de $2N$ veces, y desea mostrar al usuario dos tipos de anuncios, el anuncio 0 y el anuncio 1, $N$ veces cada uno. Dado que mostrar el mismo tipo de anuncio continuamente cada vez que se visita la página puede hacer que los usuarios se acostumbren a ellos y disminuya el efecto publicitario, se busca maximizar el efecto publicitario mediante una disposición adecuada de los dos tipos de anuncios.
Para medir el efecto publicitario de forma cuantitativa, el ingeniero de Moloco, Jongseo, ha definido un indicador llamado "aburrimiento". Para $i \leq j$, el aburrimiento de un intervalo que consiste en los anuncios desde el $i$-ésimo hasta el $j$-ésimo se define como la diferencia absoluta entre el número de anuncios 0 y el número de anuncios 1 dentro de dicho intervalo. El aburrimiento que siente el usuario finalmente es el valor máximo del aburrimiento entre todos los intervalos posibles.
Por ejemplo, si los anuncios se disponen en el orden 00110110, el aburrimiento desde el tercer anuncio hasta el séptimo anuncio es $|1 - 4| = 3$. Dado que este intervalo tiene el mayor aburrimiento, el aburrimiento final que siente el usuario es $3$.
Aunque a través de los excelentes algoritmos de Moloco se ha determinado una disposición publicitaria efectiva para aumentar la participación del usuario, Jongseo desea reducir el aburrimiento para evaluar qué tan bien funciona este indicador. Sin embargo, como el orden de los anuncios ya está establecido, para reducir el aburrimiento es necesario gastar un costo de $1$ para intercambiar dos anuncios consecutivos. Se pueden realizar tantos intercambios como se desee.
¿Cuál es el costo mínimo necesario para que el aburrimiento final que siente el usuario sea menor o igual a $K$?
Entrada
La primera línea contiene $N$ y $K$ separados por un espacio. ($1 \le K \le N \le 500\,000$)
La segunda línea contiene una cadena de longitud $2N$ compuesta únicamente por $N$ caracteres 0 y $N$ caracteres 1, que representa la disposición inicial de los anuncios.
Salida
Imprima el costo mínimo necesario para que el aburrimiento sea menor o igual a $K$.
Si el aburrimiento de la secuencia de anuncios dada ya es menor o igual a $K$, imprima 0.
Se puede demostrar que para todas las entradas posibles, siempre es posible reducir el aburrimiento a $1$. Es decir, siempre existe una solución.
Ejemplos
Entrada 1
4 2 00110110
Salida 1
1
Entrada 2
4 2 11110000
Salida 2
3
Entrada 3
4 1 10011001
Salida 3
2