Problem
Max 在她的笔记本上写了两个长度为 n 的字符串 s 和长度为 m 的 t，由字母“a”组成；和“b”拉丁字母。此外，Max 知道字符串 t 具有“laquo;abab...”的形式，即字母“a”位于字符串的奇数位置，而字母 -mdash; "b".
突然，早上，麦克斯发现有人弄乱了她的琴弦。部分s已改为“?”。
我们称位置序列 i, i + 1, ..., i + m - 1 为字符串 t 在 s 中的出现，如果 1 ≤&thinsp ;i ≤ n - m + 1 和 t
1 = s
i, t
2 = s
i + 1, ..., t
m = s
i + m - 1.
字符串 s 的美感被衡量为字符串 t 在其中非重叠出现的最大次数。 Max可以替换一些“？”在“一个”或“b” （不同位置的字符可以用不同的字母代替）。 Max 想要进行替换，使字符串 s 的美感尽可能大。在所有这些选项中，她希望尽可能少地替换“？”字符。找出她必须进行多少次替换。
输入：
第一行包含一个整数 n (1 ≤ n ≤ 10
5) —字符串长度 s.
输入的第二行包含一个长度为 n 的字符串 s，仅由字母“a”组成；和“b”拉丁字母表，以及符号“?”。
第三行包含整数 m (1 ≤ m ≤ 10
5) —字符串长度 t。字符串 t 本身包含“a”；在奇怪的位置，和“b”在偶数上。
输出：
打印单个整数——为了使字符串 s 的美观尽可能大，Vasya 必须进行的最少替换次数。
示例：
<正文>
| 输入 |
输出 |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
说明：
在第一个示例中，字符串 t 的形式为“a”。唯一的最优选择——替换所有字符“？”到“a”。
在第二个例子中，使用两个替换，你可以得到字符串“aba?aba??”。您不能获得超过两个条目。