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
//package com.company;

import java.io.*;
import java.util.*;

public class Main {

    public static class Task {
        int n, l;
        int k;
        int[] on;
        int[] use; // number of segments
        int[] realCost; // number of cases (smaller the better)
        boolean better(int use1, int realCost1, int use2, int realCost2) {
            return realCost1 < realCost2 || (realCost1 == realCost2 && use1 < use2);
        }

        int[] run(int cost) { // use, realCost
            Arrays.fill(use, n);
            Arrays.fill(realCost, n);
            use[0] = realCost[0] = 0;
            for (int i = 0; i < n; i++) {
                if (better(use[i], realCost[i] + on[i], use[i + 1], realCost[i + 1])) {
                    use[i + 1] = use[i];
                    realCost[i + 1] = realCost[i] + on[i];
                }
                int next = Math.min(n, i + l);
                if (better(use[i] + 1, realCost[i] + cost, use[next], realCost[next])) {
                    use[next] = use[i] + 1;
                    realCost[next] = realCost[i] + cost;
                }
            }
            return new int[]{use[n], realCost[n] - k * cost}; // will not overflow when use[n] <= k
        }

        int search() {
            int lo = 0, hi = 1000000;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                int[] r = run(mid);
                if (r[0] > k) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            int[] r = run(lo);
            while (r[0] > k) r = run(++lo);
            return r[1];
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            n = sc.nextInt();
            k = sc.nextInt();
            l = sc.nextInt();
            String s = sc.next();
            on = new int[n];
            use = new int[n + 1];
            realCost = new int[n + 1];
            for (int i = 0; i < n; i++) {
                on[i] = s.charAt(i) >= 'a' ? 1 : 0;
            }
            int ans1 = search();
            for (int i = 0; i < n; i++) {
                on[i] = s.charAt(i) <= 'Z' ? 1 : 0;
            }
            int ans2 = search();
            pw.println(Math.min(ans1, ans2));
        }
    }

    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("input"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("input"));


        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}