4041. [USACO24 Open Gold]Cowreography

【题目描述】

奶牛们组了一支舞蹈队，$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`。

【输出格式】

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

【样例1输入】

4 1
0111
1110

【样例1输出】

3

【样例2输入】

5 2
11000
00011

【样例2输出】

3

【样例3输入】

5 4
11000
00011

【样例3输出】

2

【样例说明】

### 样例解释 $1$

一个可能的舞蹈：

$0111 \Rightarrow 1011 \Rightarrow 1101 \Rightarrow 1110$

### 样例解释 $2$

一个可能的舞蹈：

$11000 \Rightarrow 01100 \Rightarrow 00110 \Rightarrow 00011$

### 样例解释 3

一个可能的舞蹈：

$11000 \Rightarrow 10010 \Rightarrow 00011$

【样例4输入输出】

点击下载样例4

【数据规模与约定】

- 测试点 $1-2$：$K=1$。

- 测试点 $3-4$：两个字符串各至多包含 $8$ 个 $1$。

- 测试点 $5-12$：$N\le 5000$。

- 测试点 $13-20$：没有额外限制。

【来源】

USACO