CF900E.Maximum Questions

Vasya wrote down two strings s of length n and t of length m consisting of small English letters 'a' and 'b'. What is more, he knows that string t has a form "abab...", namely there are letters 'a' on odd positions and letters 'b' on even positions.

Suddenly in the morning, Vasya found that somebody spoiled his string. Some letters of the string s were replaced by character '?'.

Let's call a sequence of positions i, i + 1, ..., i + m - 1 as occurrence of string t in s, if 1 ≤ i ≤ n - m + 1 and _t_1 = s__i, _t_2 = s__i + 1, ..., t__m = s__i + m - 1.

The boy defines the beauty of the string s as maximum number of disjoint occurrences of string t in s. Vasya can replace some letters '?' with 'a' or 'b' (letters on different positions can be replaced with different letter). Vasya wants to make some replacements in such a way that beauty of string s is maximum possible. From all such options, he wants to choose one with the minimum number of replacements. Find the number of replacements he should make.

瓦西娅写下了两个字符串：长度为 $n$ 的字符串 $s$ 和长度为 $m$ 的字符串 $t$，它们均由小写字母 'a' 和 'b' 组成。此外，他已知字符串 $t$ 具有形式 "abab..."，即在奇数位置上为字母 'a'，在偶数位置上为字母 'b'。

然而，第二天早上瓦西娅发现有人弄坏了他的字符串——字符串 $s$ 中的某些字符被替换成了字符 '?'。

我们称位置序列 $i,\,i+1,\,...,\,i+m-1$ 为字符串 $t$ 在 $s$ 中的一个出现（occurrence），当且仅当 $1 \le i \le n - m + 1$，且满足

$$t_1 = s_i,\quad t_2 = s_{i+1},\quad ...,\quad t_m = s_{i+m-1}.$$

该男孩将字符串 $s$ 的**优美度（beauty）**定义为 $s$ 中互不相交（disjoint）的 $t$ 的出现个数的最大值。瓦西娅可以将若干 '?' 替换为 'a' 或 'b'（不同位置可替换为不同字母）。他希望进行若干替换，使得字符串 $s$ 的优美度尽可能大；在所有能达到最大优美度的替换方案中，他希望选择替换次数最少的一种。请计算他所需的最少替换次数。

The first line contains a single integer n (1 ≤ n ≤ 105) — the length of s.

The second line contains the string s of length n. It contains small English letters 'a', 'b' and characters '?' only.

The third line contains a single integer m (1 ≤ m ≤ 105) — the length of t. The string t contains letters 'a' on odd positions and 'b' on even positions.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，其中仅包含小写英文字母 'a'、'b' 以及字符 '?'。

第三行包含一个整数 $m$（$1 \leq m \leq 10^5$）——字符串 $t$ 的长度。字符串 $t$ 在奇数位置上为字母 'a'，在偶数位置上为字母 'b'。

Print the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string s the maximum possible.

输出唯一的整数——Vasya 为使字符串 $s$ 的“美观度”达到最大可能值所需执行的最少替换次数。

In the first sample string t has a form 'a'. The only optimal option is to replace all characters '?' by 'a'.

In the second sample using two replacements we can make string equal to "aba?aba??". It is impossible to get more than two occurrences.

在第一个样例中，字符串 $t$ 的形式为 'a'。唯一最优的方案是将所有字符 '?' 替换为 'a'。

在第二个样例中，通过两次替换，我们可以使字符串变为 "aba?aba??"。无法获得超过两次的出现次数。