← 返回题目列表

Codeforces · 1279/F

F. 新年和处理变化

中文机器翻译题面 查看原题

新年快到了。所以是时候改变 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