新年快到了。所以是时候改变 codeforces 的处理方式了。米什卡想要改变他的名字,但要以这样的方式让人们不会忘记他是谁。
为了使其正常工作,他只允许更改字母大小写。更正式地说,在一次句柄更改期间,他可以选择其句柄 $$$[i; 的任何部分; i + l - 1]$$$ 并将 tolower 或 toupper 应用于此段上其句柄的所有字母(更正式地,将所有大写字母替换为相应的小写字母,反之亦然)。对于所有更改,长度 $$$l$$$ 都是固定的。
因为不允许太频繁地更改 codeforces 句柄,所以 Mishka 最多可以执行 $$$k$$$ 这样的操作。最优变化顺序后,$$$min(lower, upper)$$$(其中$$$lower$$$为小写字母个数,$$$upper$$$为大写字母个数)的最小值是多少?
输入
输入的第一行包含三个整数 $$$n、k$$$ 和 $$$l$$$ ($$$1 \le n, k, l \le 10^6, l \le n)$$$ — Mishka 句柄的长度、更改的次数和段的长度。
输入的第二行包含一个字符串 $$$s$$$,由 $$$n$$$ 小写和大写拉丁字母组成——Mishka 的句柄。
输出
打印一个整数 - Mishka 按照问题陈述中描述的方式最多更改句柄 $$$k$$$ 次后 $$$min(lower, upper)$$$ 的最小值。
示例
输入 #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