Problem
Max avait deux chaînes s de longueur n et t de longueur m écrites dans son cahier, composées des lettres "a" ; et B" alphabet latin. De plus, Max sait que la chaîne t a la forme "abab...", c'est-à-dire que la lettre "a" est sur les positions impaires de la chaîne, et la lettre — "b".
Soudain, le matin, Max a découvert que quelqu'un avait foiré ses cordes. Certains des s ont été changés en "?".
Appelons la séquence de positions i, i + 1, ..., i + m - 1 une occurrence de la chaîne t dans s, si 1 ≤&thinsp ;i ≤ n - m + 1 et t
1 = s
i, t
2 &thinsp ;= s
i + 1, ..., t
m = s
i + m - 1.
La beauté de la chaîne s est mesurée comme le nombre maximum d'occurrences non superposées de la chaîne t dans celle-ci. Max peut remplacer certains des "?" sur un" ou "b" (les caractères à des positions différentes peuvent être remplacés par des lettres différentes). Max veut faire des substitutions pour que la beauté de la chaîne s soit aussi grande que possible. De toutes ces options, elle souhaite remplacer le moins de caractères "?" possible. Découvrez combien de substitutions elle doit faire.
Saisie :
La première ligne contient un seul entier n (1 ≤ n ≤ 10
5) — longueur de chaîne s.
La deuxième ligne de l'entrée contient une chaîne s de longueur n, composée uniquement des lettres "a" ; et B" l'alphabet latin, ainsi que les symboles «?».
La troisième ligne contient l'entier m (1 ≤ m ≤ 10
5) — longueur de chaîne t. La chaîne t elle-même contient "a" ; dans des positions impaires, et "b" sur les nombres pairs.
Sortie :
Imprimer un seul entier — le nombre minimum de substitutions que Vasya doit effectuer afin de rendre la beauté de la chaîne le maximum possible.
Exemples :
| Entrée |
Sortie |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
Explications :
Dans le premier exemple, la chaîne t est de la forme "a". La seule option optimale — remplacer tous les caractères "?" à «a».
Dans le deuxième exemple, en utilisant deux remplacements, vous pouvez obtenir la chaîne "aba?aba??". Vous ne pouvez pas obtenir plus de deux entrées.