#include <bits/stdc++.h>
using namespace std;
static int LOCAL = 0;
const long long int mod = 1000000007ll;
const long long int MOD = 1000000009ll;
const long long int INF = LLONG_MAX / 10;
const int inf = INT_MAX / 2;
long long int count_bit(long long int _x) {
  long long int _ret = 0;
  while (_x) {
    if (_x % 2 == 1) _ret++;
    _x /= 2;
  }
  return _ret;
}
bool check_bit(long long int _mask, long long int _i) {
  long long int x = 1;
  return (_mask & (x << _i)) == 0 ? false : true;
}
long long int set_bit(long long int _mask, long long int _i) {
  long long int x = 1;
  _mask = _mask | (x << _i);
  return _mask;
}
long long int msb(long long int _mask) {
  long long int ret = -1;
  int cnt = 0;
  while (_mask) {
    if (_mask & 1) ret = cnt;
    _mask /= 2;
    cnt++;
  }
  return ret;
}
long long int powermod(long long int _a, long long int _b,
                       long long int _m = mod) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a) % _m;
    _b /= 2;
    _a = (_a * _a) % _m;
  }
  return _r;
}
long long int power(long long int _a, long long int _b) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a);
    _b /= 2;
    _a = (_a * _a);
  }
  return _r;
}
long long int add(long long int a, long long int b, long long int m = mod) {
  long long int x = a + b;
  while (x >= m) x -= m;
  return x;
}
long long int sub(long long int a, long long int b, long long int m = mod) {
  long long int x = a - b;
  while (x < 0) x += m;
  return x;
}
long long int mul(long long int a, long long int b, long long int m = mod) {
  long long int x = a * b;
  x %= m;
  return x;
}
long long int gcd(long long int a, long long int b) {
  while (a && b) a > b ? a %= b : b %= a;
  return a + b;
}
long long int lcm(long long int a, long long int b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
struct cmp {
  bool operator()(pair<int, int> const& l, pair<int, int> const& r) {
    if (l.first != r.first)
      return l.first > r.first;
    else
      return l.second > r.second;
  }
} myobject;
int n, m;
string second;
int pre[2][2][100010], que[100010];
pair<int, int> dp[100010];
int main() {
  LOCAL = 0;
  if (LOCAL) {
    freopen("C:\\Users\\Smit Patel\\Downloads\\D-large.in", "r", stdin);
    freopen("C:\\Users\\Smit Patel\\Desktop\\out.txt", "w", stdout);
  }
  cin >> n >> second >> m;
  memset(pre, 0, sizeof(pre));
  memset(que, 0, sizeof(que));
  for (int i = 0; i <= n; i++) dp[i] = {0, inf};
  dp[0] = {0, 0};
  second = '-' + second;
  for (int i = 1; i <= n; i++) {
    if (second[i] == 'a' || second[i] == '?') {
      if (i & 1)
        pre[0][1][i] = 1;
      else
        pre[0][0][i] = 1;
    }
    if (second[i] == 'b' || second[i] == '?') {
      if (i & 1)
        pre[1][1][i] = 1;
      else
        pre[1][0][i] = 1;
    }
    if (second[i] == '?') que[i] = 1;
    que[i] += que[i - 1];
    for (int j = 0; j <= 1; j++)
      for (int k = 0; k <= 1; k++) pre[j][k][i] += pre[j][k][i - 1];
  }
  int l, ll, c, cc;
  if (m & 1)
    l = 0, ll = 1, c = m / 2 + 1, cc = m / 2;
  else
    l = 1, ll = 0, c = m / 2, cc = m / 2;
  for (int i = 1; i <= n; i++) {
    dp[i] = dp[i - 1];
    if (i - m < 0) continue;
    if (pre[l][i & 1][i] - pre[l][i & 1][i - m] == c &&
        pre[ll][!(i & 1)][i] - pre[ll][!(i & 1)][i - m] == cc) {
      if (dp[i].first < dp[i - m].first + 1) {
        dp[i].first = dp[i - m].first + 1;
        dp[i].second = dp[i - m].second + que[i] - que[i - m];
      } else if (dp[i].first == dp[i - m].first + 1)
        dp[i].second =
            min(dp[i].second, dp[i - m].second + que[i] - que[i - m]);
    }
  }
  cout << dp[n].second;
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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

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

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
static int LOCAL = 0;
const long long int mod = 1000000007ll;
const long long int MOD = 1000000009ll;
const long long int INF = LLONG_MAX / 10;
const int inf = INT_MAX / 2;
long long int count_bit(long long int _x) {
  long long int _ret = 0;
  while (_x) {
    if (_x % 2 == 1) _ret++;
    _x /= 2;
  }
  return _ret;
}
bool check_bit(long long int _mask, long long int _i) {
  long long int x = 1;
  return (_mask & (x << _i)) == 0 ? false : true;
}
long long int set_bit(long long int _mask, long long int _i) {
  long long int x = 1;
  _mask = _mask | (x << _i);
  return _mask;
}
long long int msb(long long int _mask) {
  long long int ret = -1;
  int cnt = 0;
  while (_mask) {
    if (_mask & 1) ret = cnt;
    _mask /= 2;
    cnt++;
  }
  return ret;
}
long long int powermod(long long int _a, long long int _b,
                       long long int _m = mod) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a) % _m;
    _b /= 2;
    _a = (_a * _a) % _m;
  }
  return _r;
}
long long int power(long long int _a, long long int _b) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a);
    _b /= 2;
    _a = (_a * _a);
  }
  return _r;
}
long long int add(long long int a, long long int b, long long int m = mod) {
  long long int x = a + b;
  while (x >= m) x -= m;
  return x;
}
long long int sub(long long int a, long long int b, long long int m = mod) {
  long long int x = a - b;
  while (x < 0) x += m;
  return x;
}
long long int mul(long long int a, long long int b, long long int m = mod) {
  long long int x = a * b;
  x %= m;
  return x;
}
long long int gcd(long long int a, long long int b) {
  while (a && b) a > b ? a %= b : b %= a;
  return a + b;
}
long long int lcm(long long int a, long long int b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
struct cmp {
  bool operator()(pair<int, int> const& l, pair<int, int> const& r) {
    if (l.first != r.first)
      return l.first > r.first;
    else
      return l.second > r.second;
  }
} myobject;
int n, m;
string second;
int pre[2][2][100010], que[100010];
pair<int, int> dp[100010];
int main() {
  LOCAL = 0;
  if (LOCAL) {
    freopen("C:\\Users\\Smit Patel\\Downloads\\D-large.in", "r", stdin);
    freopen("C:\\Users\\Smit Patel\\Desktop\\out.txt", "w", stdout);
  }
  cin >> n >> second >> m;
  memset(pre, 0, sizeof(pre));
  memset(que, 0, sizeof(que));
  for (int i = 0; i <= n; i++) dp[i] = {0, inf};
  dp[0] = {0, 0};
  second = '-' + second;
  for (int i = 1; i <= n; i++) {
    if (second[i] == 'a' || second[i] == '?') {
      if (i & 1)
        pre[0][1][i] = 1;
      else
        pre[0][0][i] = 1;
    }
    if (second[i] == 'b' || second[i] == '?') {
      if (i & 1)
        pre[1][1][i] = 1;
      else
        pre[1][0][i] = 1;
    }
    if (second[i] == '?') que[i] = 1;
    que[i] += que[i - 1];
    for (int j = 0; j <= 1; j++)
      for (int k = 0; k <= 1; k++) pre[j][k][i] += pre[j][k][i - 1];
  }
  int l, ll, c, cc;
  if (m & 1)
    l = 0, ll = 1, c = m / 2 + 1, cc = m / 2;
  else
    l = 1, ll = 0, c = m / 2, cc = m / 2;
  for (int i = 1; i <= n; i++) {
    dp[i] = dp[i - 1];
    if (i - m < 0) continue;
    if (pre[l][i & 1][i] - pre[l][i & 1][i - m] == c &&
        pre[ll][!(i & 1)][i] - pre[ll][!(i & 1)][i - m] == cc) {
      if (dp[i].first < dp[i - m].first + 1) {
        dp[i].first = dp[i - m].first + 1;
        dp[i].second = dp[i - m].second + que[i] - que[i - m];
      } else if (dp[i].first == dp[i - m].first + 1)
        dp[i].second =
            min(dp[i].second, dp[i - m].second + que[i] - que[i - m]);
    }
  }
  cout << dp[n].second;
  return 0;
}

```