Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Maximum Questions

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya 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.

Input

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.

Output

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

Examples

Input

5

bb?a?

1

Output

2

Input

9

ab??ab???

3

Output

2

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 17:36:54 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|