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
/**
 * BaZ :D
 */

import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main
{
    static MyScanner scan;
    static PrintWriter pw;
    static long MOD = 1_000_000_007;
    static long INF = 1_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null, null, "BaZ", 1 << 27) {
            public void run() {
                try {
                    solve();
                } catch (Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }
    static int n,k,l,pref[];
    static long dp[],cnt[];
    static void solve() throws IOException
    {
        //initIo(true);
        initIo(false);
        StringBuilder sb = new StringBuilder();
        int n = ni(), k = ni(), l = ni();
        char c[] = ne().toCharArray();
        int arr[] = new int[n];
        int comp_arr[] = new int[n];
        for(int i=0;i<n;++i) {
            if(Character.isUpperCase(c[i])) {
                arr[i] = 1;
            }
            else {
                comp_arr[i] = 1;
            }
        }
        long ans = min(calc(arr, n, k, l), calc(comp_arr,n,k,l));
        pl(ans);
        pw.flush();
        pw.close();
    }
    static long calc(int arr[], int N, int K, int L) {
        k = K;
        n = N;
        l = L;
        pref = new int[n];
        for(int i=0;i<n;++i) {
            pref[i] = arr[i];
            if(i>0) {
                pref[i]+=pref[i-1];
            }
        }
        dp = new long[n+1];
        cnt = new long[n+1];
//        pa("arr", arr);
//        pa("pref", pref);
        long low = 0, high = 1_000_000_000L, mid, ans = high;
        while(low<=high) {
            mid = (low+high)>>1;
            //pa("arr", arr);
            f(mid);
            if(cnt[0] <= k) {
                ans = mid;
                high = --mid;
            }
            else {
                low = ++mid;
            }
        }
        //pa("arr", arr);
        f(ans);
        //pl("ans : "+ans+" dp : "+dp[0]+" cnt : "+cnt[0]);
        return pref[n-1] - (dp[0] + K*ans);
    }
    static long f(long lambda) {
        //pl("lambda : "+lambda);
        //pa("pref", pref);
        dp[n] = 0;
        cnt[n] = 0;
        for(int i=n-1;i>=0;--i) {
            long start_pe = dp[min(i+l, n)] + pref[min(i+l-1, n-1)] - (i==0 ? 0 : pref[i-1]) - lambda;
            long aise = dp[i+1];
            if(start_pe > aise) {
                //pl("at "+i+" start pe is better");
                dp[i] = start_pe;
                cnt[i] = cnt[min(i+l, n)] + 1;
            }
            else if(start_pe == aise) {
                dp[i] = start_pe;
                cnt[i] = min(cnt[i+1], cnt[min(i+l, n)] + 1);
            }
            else {
                dp[i] = aise;
                cnt[i] = cnt[i+1];
            }
        }
//        pa("dp", dp);
//        pa("cnt", cnt);
        return dp[0];
    }
    static void initIo(boolean isFileIO) throws IOException {
        scan = new MyScanner(isFileIO);
        if(isFileIO) {
            pw = new PrintWriter("/Users/amandeep/Desktop/output.txt");
        }
        else {
            pw = new PrintWriter(System.out, true);
        }
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static String ne() throws IOException
    {
        return scan.next();
    }
    static String nel() throws IOException
    {
        return scan.nextLine();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static class MyScanner
    {
        BufferedReader br;
        StringTokenizer st;
        MyScanner(boolean readingFromFile) throws IOException
        {
            if(readingFromFile) {
                br = new BufferedReader(new FileReader("/Users/amandeep/Desktop/input.txt"));
            }
            else {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
        }
        String nextLine()throws IOException
        {
            return br.readLine();
        }
        String next() throws IOException
        {
            if(st==null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws IOException
        {
            return Integer.parseInt(next());
        }
        long nextLong() throws IOException
        {
            return Long.parseLong(next());
        }
        double nextDouble() throws IOException
        {
            return Double.parseDouble(next());
        }
    }
}