New Year is getting near. So it's time to change handles on codeforces. Mishka wants to change his handle but in such a way that people would not forget who he is.

To make it work, he only allowed to change letters case. More formally, during one handle change he can choose any segment of his handle [i; i + l - 1] and apply tolower or toupper to all letters of his handle on this segment (more fomally, replace all uppercase letters with corresponding lowercase or vice versa). The length l is fixed for all changes.

Because it is not allowed to change codeforces handle too often, Mishka can perform at most k such operations. What is the minimum value of min(lower, upper) (where lower is the number of lowercase letters, and upper is the number of uppercase letters) can be obtained after optimal sequence of changes?

Input

The first line of the input contains three integers n, k and l (1 ≤ n, k, l ≤ 10^6, l ≤ n) — the length of Mishka's handle, the number of changes and the length of the segment.

The second line of the input contains one string s, consisting of n lowercase and uppercase Latin letters — Mishka's handle.

Output

Print one integer — the minimum value of min(lower, upper) after that Mishka change his handle at most k times in a way described in the problem statement.

Examples

Input


7 1 4
PikMike


Output


0


Input


15 2 2
AaAaAAaaAAAAaaA


Output


2


Input


14 2 6
aBcdEFGHIJklMn


Output


0


Input


9 2 2
aAaAAAaaA


Output


1
#include <bits/stdc++.h>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first - r.first, l.second - r.second};
}
long long pr[10000100];
long long inv[10000010];
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = ((long long)pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
  }
}
long long n, l, k;
long long a[1000020] = {};
pair<long long, long long> dp[1000020];
pair<long long, long long> ch(long long r) {
  dp[0] = make_pair(0, 0);
  for (long long i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] + make_pair(a[i], 0);
    dp[i] = min(dp[i], dp[max(0ll, i - l)] + make_pair(r, 1));
  }
  return dp[n];
}
long long solve() {
  long long e;
  if (ch(0).second <= k)
    e = 0;
  else {
    long long si = 0, ue = 1000000007;
    while (ue - si > 1) {
      long long me = (ue + si) / 2;
      if (ch(me).second <= k)
        ue = me;
      else
        si = me;
    }
    e = ue;
  }
  pair<long long, long long> z = ch(e);
  return z.first - e * k;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> k >> l;
  string s;
  cin >> s;
  for (long long i = 0; i < n; i++) a[i + 1] = (s[i] <= 'Z');
  long long y1 = solve();
  for (long long i = 1; i <= n; i++) a[i] ^= 1;
  long long y2 = solve();
  cout << min(y1, y2) << endl;
  return 0;
}
