Problem
Max tenía dos cadenas s de longitud n y t de longitud m escritas en su cuaderno, que constaban de las letras "a"; y B" Alfabeto latino. Además, Max sabe que la cadena t tiene la forma «abab...», es decir, la letra «a» está en las posiciones impares de la cadena, y la letra — "b".
De repente, por la mañana, Max descubrió que alguien había estropeado sus hilos. Algunas de las s se han cambiado a "?".
Llamemos a la secuencia de posiciones i, i + 1, ..., i + m - 1 una ocurrencia de la cadena t en s, si 1 ≤&thinsp ;i ≤ n - m + 1 y t
1 = s
i, t
2 = s
i + 1, ..., t
m = s
i + m - 1.
La belleza de la cadena s se mide como el número máximo de ocurrencias no superpuestas de la cadena t en ella. Max puede reemplazar algunos de los "?" en un" o "b" (los caracteres en diferentes posiciones pueden ser reemplazados por letras diferentes). Max quiere hacer sustituciones para que la belleza de la cadena s sea lo más grande posible. De todas estas opciones, quiere reemplazar la menor cantidad posible de caracteres "?". Averigüe cuántas sustituciones tiene que hacer.
Entrada:
La primera línea contiene un único número entero n (1 ≤ n ≤ 10
5) — longitud de cadena s.
La segunda línea de la entrada contiene una cadena s de longitud n, que consta solo de las letras "a"; y B" el alfabeto latino, así como los símbolos «?».
La tercera línea contiene el entero m (1 ≤ m ≤ 10
5) — longitud de la cuerda t. La propia cadena t contiene "a"; en posiciones impares, y "b" en números pares.
Salida:
Imprime un solo entero — el número mínimo de sustituciones que Vasya debe hacer para que la belleza de la cuerda sea la máxima posible.
Ejemplos:
| Entrada |
Salida |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
Explicaciones:
En el primer ejemplo, la cadena t tiene la forma "a". La única opción óptima — reemplazar todos los caracteres "?" a «a».
En el segundo ejemplo, usando dos reemplazos, puede obtener la cadena "aba?aba??". No puede obtener más de dos entradas.