Problem
Max had two strings s of length n and t of length m written in her notebook, consisting of the letters "a"; and "b" Latin alphabet. Moreover, Max knows that the string t has the form «abab...», that is, the letter «a» is on the odd positions of the string, and the letter — "b".
Suddenly, in the morning, Max discovered that someone had messed up her string s. Some of the s's have been changed to "?".
Let's call the sequence of positions i, i + 1, ..., i + m - 1 an occurrence of string t in s, if 1 ≤ i ≤ n - m + 1 and t
1 = s
i, t
2&thinsp ;= s
i + 1, ..., t
m = s
i + m - 1.
The beauty of string s is measured as the maximum number of non-overlapping occurrences of string t in it. Max can replace some of the "?" on "a" or "b" (characters in different positions can be replaced by different letters). Max wants to make substitutions so that the beauty of the string s is as large as possible. Of all these options, she wants to replace as few "?" characters as possible. Find out how many substitutions she has to make.
Input:
The first line contains a single integer n (1 ≤ n ≤ 10
5) — string length s.
The second line of the input contains a string s of length n, consisting only of the letters "a"; and "b" the Latin alphabet, as well as the symbols «?».
The third line contains the integer m (1 ≤ m ≤ 10
5) — string length t. The string t itself contains "a"; in odd positions, and "b" on even numbers.
Output:
Print a single integer — the minimum number of substitutions that Vasya must make in order to make the beauty of the string s the maximum possible.
Examples:
| Input |
Output |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
Explanations:
In the first example, the string t is of the form "a". The only optimal option — replace all characters "?" to «a».
In the second example, using two replacements, you can get the string "aba?aba??". You cannot get more than two entries.