Problem 1. Cowreography

USACO 2024 US Open Contest, Gold

奶牛们组了一支舞蹈队，Farmer John 是她们的编舞！舞蹈队最新而最精彩的舞蹈有 $N$ 头奶牛（$2 \le N \le 10^6$）排成一行。舞蹈中的每次动作都涉及两头奶牛，至多相距 $K$ 个位置（$1 \le K < N$），优雅地跳起并降落在对方的位置上。

队伍中有两种奶牛——更赛牛（Guernsey）和荷斯坦牛（Holstein）。因此，Farmer John 将这一舞蹈记录为一系列

长为 $N$ 的 01 字符串

，其中 $0$ 代表更赛牛，$1$ 代表荷斯坦牛，整个字符串表示奶牛在这一行中是如何排列的。

不幸的是，Farmer Nhoj（对手团队的编舞）蓄意破坏了这一舞蹈，并清除了除第一个和最后一个 01 字符串之外的所有内容！由于一场大型比赛即将开始，Farmer John 必须抓紧每一秒重建这一舞蹈。

给定这两个 01 字符串，帮助 Farmer John 求出舞蹈中的最小动作数量！

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$ 和 $K$。

第二行包含第一个 01 字符串。

第三行包含最后一个 01 字符串。

输入保证两个 01 字符串包含相同数量的 1。

输出格式（输出至终端 / 标准输出）：

输出舞蹈中的最小动作数量。

输入样例：

4 1
0111
1110

输出样例：

3

一个可能的舞蹈：

0111 -> 1011 -> 1101 -> 1110

输入样例：

5 2
11000
00011

输出样例：

3

一个可能的舞蹈：

11000 -> 01100 -> 00110 -> 00011

输入样例：

5 4
11000
00011

输出样例：

2

一个可能的舞蹈：

11000 -> 10010 -> 00011

测试点性质： 测试点 4-5：$K=1$。测试点 6-7：两个字符串各至多包含 $8$ 个 1。测试点 8-15：$N\le 5000$。测试点 16-23：没有额外限制。

供题：Benjamin Qi