Problem
Max tinha duas strings s de comprimento n e t de comprimento m escritas em seu caderno, consistindo nas letras "a"; e B" alfabeto latino. Além disso, Max sabe que a string t tem a forma «abab...», ou seja, a letra «a» está nas posições ímpares da string, e a letra — "b".
De repente, pela manhã, Max descobriu que alguém havia bagunçado seus fios. Alguns dos s foram alterados para "?".
Vamos chamar a sequência de posições i, i + 1, ..., i + m - 1 uma ocorrência da string t em 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.
A beleza da string s é medida como o número máximo de ocorrências não sobrepostas da string t nela. Max pode substituir alguns dos "?" com um" ou "b" (caracteres em posições diferentes podem ser substituídos por letras diferentes). Max quer fazer substituições para que a beleza da string s seja a maior possível. De todas essas opções, ela deseja substituir o mínimo possível de caracteres "?". Descubra quantas substituições ela tem que fazer.
Entrada:
A primeira linha contém um único inteiro n (1 ≤ n ≤ 10
5) — comprimento da string s.
A segunda linha da entrada contém uma string s de comprimento n, consistindo apenas nas letras "a"; e B" o alfabeto latino, bem como os símbolos «?».
A terceira linha contém o inteiro m (1 ≤ m ≤ 10
5) — comprimento da corda t. A própria string t contém "a"; em posições ímpares, e "b" em números pares.
Saída:
Imprima um único inteiro — o número mínimo de substituições que Vasya deve fazer para tornar a beleza dos fios o máximo possível.
Exemplos:
| Entrada |
Saída |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
Explicações:
No primeiro exemplo, a string t está na forma "a". A única opção ideal — substitua todos os caracteres "?" para «a».
No segundo exemplo, usando duas substituições, você pode obter a string "aba?aba??". Você não pode obter mais de duas entradas.