新年与用户名更改

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$、仅含大小写拉丁字母的字符串。一次操作可以选择一个长度恰为 $l$ 的连续子串，并把其中所有字母全部转换为小写，或全部转换为大写。至多进行 $k$ 次操作。

设最终字符串中小写字母和大写字母的数量分别为 $lower$ 和 $upper$。求 $\min(lower,upper)$ 的最小可能值。

输入格式

第一行包含三个整数 $n,k,l$。

第二行包含长度为 $n$ 的字符串 $s$。

输出格式

输出一个整数，表示答案。

样例输入 1

7 1 4
PikMike

样例输出 1

0

样例输入 2

15 2 2
AaAaAAaaAAAAaaA

样例输出 2

2

样例输入 3

14 2 6
aBcdEFGHIJklMn

样例输出 3

0

样例输入 4

9 2 2
aAaAAAaaA

样例输出 4

1

数据范围

$1\le n,k,l\le 10^6$，$l\le n$。