样例下载

题目描述

小明有两个长度均为 $N$ 且仅包含 0, 1 两种字符的字符串 $S, T$，并且 $S, T$ 含有的 0 的数量相同。

小明希望将 $S$ 转换成 $T$。

为此小明找到了一个字符串编辑工具，这个工具提供的基本操作是在字符串 $S$ 中交换两个距离不超过 $K$ 的字符，即若交换两个字符 $S_i$ 与 $S_j$，则须满足 $|i-j| ≤ K$。

小明可以用编辑工具对 $S$ 进行多次字符交换，其中可以参与交换的字符能够交换任意多次。

现在小明想知道，使用编辑工具至少需要多少次交换，可以使得 $S$ 转换成 $T$？

输入格式

第一行：两个整数 $N, K$

第二行：一个长度为 $N$ 的 01 字符串 $S$。

第三行：一个长度为 $N$ 的 01 字符串 $T$。

数据保证 $S, T$ 含有的 0 的数量相同。

输出格式

一个整数，表示答案。

样例1输入

4 1
1110
0111

样例1输出

3

样例1解释

一种编辑方式是：

1 1 10 ---> 1101 ---> 1011 ---> 0111

样例2输入

4 2
1110
0111

样例2输出

2

样例2解释

一种编辑方式是：

1110 ---> 1011 ---> 0111

样例3输入

4 3
1110
0111

样例3输出

1

样例3解释

一种编辑方式是：

1110 ---> 0111

数据范围

共 25 个测试点，每个测试 4 分。全部测试点满足：$1 ≤ N ≤ 10^6, 1 ≤ K < N$。具体如下：

测试点编号	N	特殊说明
$1$	$N ≤ 5$	$K = 1$
$2-3$	$N ≤ 10$	无
$4-5$	$N = 10^6$	$K=1$
$6-7$		$S$ 中含有的 1 的个数不超过 $8$
$8-15$	$N = 5000$	无
$16-23$	$N = 10^6$
$24-25$		$K = 999999$