Maximum Questions
Contest: Codeforces Round 450 (Div. 2)
Difficulty rating: 2100
Tags: data structures, dp, strings

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 t1 = si, t2 = si + 1, ..., tm = si + 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.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
5
bb?a?
1

Example output:
2

Example input:
9
ab??ab???
3

Example output:
2

Editorial:
Let's find all positions i in string s such that occurrence t can start at position i after making some replacements.
How to find them? As t has a form "abab..." letters si, si + 2, si + 4, ..., s(i + m - 1|i + m - 2) should be equal to '?' or 'a' and si + 1, si + 3..., s(i + m - 1|i + m - 2) should be equal to '?' or 'b'. Let's calculate f[i][с] — how many consecutive letters si, si + 2, ..., s(f[i][c] - 1)·2 are equal to '?' or c.
Than it is left to verify for position i or f[i][a] ≥ cell(n / 2) and f[i][b] ≥ floor(n / 2). We found all positions where occurrence of t can start.
Remaining task can be solved using dynamic programming. Let dp[i][j] — the minimum number of replacements should be done that the number of occurrences in prefix i is exactly maximum possible minus j.
How to calculate this dp? If from position i + 1 can be started occurrence than dp[i + m][MaxOccuri + m - (MaxOccuri - j)] = best(dp[i + m][MaxOccuri + m - (MaxOccuri - j)], dp[i][j] + CountQuestionsi + 1, i + m). Where CountQuestionsi, j means the number of letter '?' in substring from position i to j and MaxOccuri means the maximum number of occurrences in prefix from position 1 to i, that can be calculated greedily.
Actually considering j > 1 is redundant. Really, if we consider such set of occurrences that exists prefix for which the number of occurrences at least two less than maximum possible than we always can find the larger set of occurrences taking the maximum possible in this prefix and maybe deleting one that intersects with the prefix.
The answer is dp[n][0].
Time complexity O(n).