Problem
Max aveva due stringhe s di lunghezza n e t di lunghezza m scritte sul suo taccuino, costituite dalle lettere "a"; e B" Alfabeto latino. Inoltre, Max sa che la stringa t ha la forma «abab...», cioè la lettera «a» si trova nelle posizioni dispari della stringa, e la lettera — "b".
All'improvviso, al mattino, Max scoprì che qualcuno le aveva incasinato le corde. Alcune delle s sono state modificate in "?".
Chiamiamo la sequenza di posizioni i, i + 1, ..., i + m - 1 occorrenza della stringa t in s, se 1 ≤&thinsp ;i ≤ n - m + 1 e t
1 = s
i, t
2 &thinsp ;= s
i + 1, ..., t
m = s
i + m - 1.
La bellezza della stringa s è misurata come il numero massimo di occorrenze non sovrapposte della stringa t in essa contenute. Max può sostituire alcuni dei "?" su "a" o "b" (i caratteri in posizioni diverse possono essere sostituiti da lettere diverse). Max vuole fare delle sostituzioni in modo che la bellezza della stringa s sia la più grande possibile. Di tutte queste opzioni, desidera sostituire il minor numero possibile di caratteri "?". Scopri quante sostituzioni deve effettuare.
Inserimento:
La prima riga contiene un singolo numero intero n (1 ≤ n ≤ 10
5) — lunghezza stringa s.
La seconda riga dell'input contiene una stringa s di lunghezza n, composta solo dalle lettere "a"; e B" l'alfabeto latino, così come i simboli «?».
La terza riga contiene il numero intero m (1 ≤ m ≤ 10
5) — lunghezza della corda t. La stringa t stessa contiene "a"; in posizioni dispari, e "b" sui numeri pari.
Uscita:
Stampa un singolo numero intero — il numero minimo di sostituzioni che Vasya deve effettuare per rendere la bellezza della corda la massima possibile.
Esempi:
| Input |
Uscita |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
Spiegazioni:
Nel primo esempio, la stringa t è della forma "a". L'unica opzione ottimale — sostituire tutti i caratteri "?" a «a».
Nel secondo esempio, usando due sostituzioni, puoi ottenere la stringa "aba?aba??". Non puoi ottenere più di due voci.