题目描述

给定一个长度为 $n$ 的 01 串，你需要将它划分成若干段，每一段的长度都不超过 $m$，且满足以下两种条件之一：

1. 这个段中全部为 $0$ 或全部为 $1$.
2. 这个段中 $0,1$ 数量之差不超过 $k$.

你需要求出该 01 串合法的划分最少要多少段。

输入格式

第一行输入三个整数 $n,m,k$，分别表示 $01$ 串的长度，段的长度限制，条件 $1$ 中 $0,1$ 数量差的限制。

接下来一行，输入一个长度为 $n$ 的 $01$ 串，表示该 $01$ 串。

输出格式

一行，输出一个正整数，最少划分段数。

样例 #1

样例输入 #1

5 4 1
01110

样例输出 #1

2

样例 #2

样例输入 #2

20 5 1
10111101010011000100

样例输出 #2

6

提示

样例 1 解释：

一种符合条件的划分方式是 (01,110).

数据范围：

其中，性质 A 为：$01$ 串随机生成，每一位均有一半的概率为 $0$,一半的概率为 $1$.\
表中性质 A 一栏为 $1$ 则表示数据满足该性质。

对于 $100\%$ 的数据，满足 $n,m,k \le 10^7$

下发文件

ssfz联测 下发文件