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>
using namespace std;
const int MOD = 119 << 23 | 1;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() { return abs((int)mt()); }
void chemthan() {
  int n, k, l;
  cin >> n >> k >> l;
  chkmin(k, (n + l - 1) / l);
  string s;
  cin >> s;
  vector<int> a(n);
  for (int i = (0); i < (n); ++i) a[i] = 'a' <= s[i] && s[i] <= 'z';
  auto ff = [&]() {
    vector<int> b = a;
    for (int i = (1); i < (n); ++i) b[i] += b[i - 1];
    for (int i = (n)-1; i >= (0); --i) {
      int j = max(0, i - l + 1);
      if (j) b[i] -= b[j - 1];
    }
    auto calc = [&](long long mi) {
      vector<pair<long long, int>> dp(n);
      for (int i = (0); i < (n); ++i) {
        auto mx = i - l < 0 ? make_pair(0LL, 0) : dp[i - l];
        chkmax(dp[i], make_pair(mx.first + b[i] + mi, mx.second + 1));
        if (i) {
          chkmax(dp[i], dp[i - 1]);
        }
      }
      return dp[n - 1];
    };
    long long lo = -2e6, hi = +2e6;
    while (lo < hi) {
      long long mi = lo + (hi - lo >> 1);
      if (calc(mi).second < k) {
        lo = mi + 1;
      } else {
        hi = mi;
      }
    }
    long long mi = lo + (hi - lo >> 1);
    auto res = calc(mi);
    int sum = 0;
    for (int i = (0); i < (n); ++i) sum += a[i];
    return sum - (res.first - k * mi);
  };
  long long res = ff();
  for (int i = (0); i < (n); ++i) a[i] ^= 1;
  chkmin(res, ff());
  cout << res << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}
