奶龙与奶农 (Hard Version)

题目描述

奶龙和奶农是两个对立的物种。一个子区域内，一旦奶龙的个数过多，奶龙就会吃掉奶农；同样，如果奶农的数量过多，奶农给就会杀死奶龙。只有奶龙和奶农数量相差不超过 $k$, 或一个子区域只有奶龙或奶农时，这个子区域才会平衡。形式化地:

且满足以下两种条件之一：

1. 这个子区域中全部为奶龙或全部为奶农.
2. 这个段中 $0,1$ 数量之差不超过 $k$.

你需要将整个区域划分成长度不超过 $m$ 的若干子区域，且每一段都是平衡的. 求该区域最少划分为多少段子区域。

输入格式

第一行输入三个整数 $n,m,k$，分别表示区域的长度，子区域的长度限制，条件 $2$ 中奶龙与奶农数量差的限制。

接下来一行，输入一个长度为 $n$ 的 $01$, 代表 $1 \times n$ 的区域，其中某个位置为 $0$ 表示这个格子内有一只奶龙，$1$ 表示这个格子内有一只奶农。

输出格式

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

样例 #1

样例输入 #1

5 4 1
01110

样例输出 #1

2

样例 #2

样例输入 #2

20 5 1
10111101010011000100

样例输出 #2

6

提示

样例 1 解释：

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

数据范围：

其中，性质 A 为：奶农与奶农随机生成，每一位均有一半的概率为奶龙,一半的概率为奶农.

表中性质 A 一栏为 $1$ 则表示数据满足该性质。

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