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. The first line contains a single integer n ( 1 ≤ n ≤ 10 5 ) — 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 ≤ 10 5 ) — the length of t . The string t contains letters ' a ' on odd positions and ' b ' on even positions. Print the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string s the maximum possible. 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.