题目描述

现有由 $n$ 块小积木拼成的一个长条积木，从左到右的小积木编号依次为 $1..n$，其中第 $i$ 块小积木的颜色为 $c_i$。若$c_i$ 为 $0$ 则为红色，为$1$ 则为蓝色。

每次，你可以选中其中任意长度不超过 $k$ 的连续段积木，将其染成同一种颜色。现给定一个$01$串 $S$ 初始时每个积木的颜色，及另一个$01$串 $T$ 染色后的目标状态，请你求出为使积木从初始状态染色成目标状态，最少染色几次即可完成？

输入格式

输入共三行： 第一行，两个正整数 $n,k$ 第二行，一个长度为 $n$ 的 $01$ 串 $S$，表示初始状态 第二行，一个长度为 $n$ 的 $01$ 串 $T$，表示最终状态

输出格式

输出共一行，一个正整数表示最少染色次数

10 2
0011000111
0000111111

3

样例解释 1

第1次，将第3、4块积木染成红色。 第2次，将第5、6块积木染成蓝色。 第3次，将第7块积木染成蓝色。

10 4
0011000111
0000111111

2

样例解释 2

第1次，将第3、4块积木染成红色。 第2次，将第5-7块积木染成蓝色。

数据范围

• 对于 $30\%$的数据，$1 \leq k \leq n \leq 10$
• 对于 $60\%$的数据，$1 \leq k \leq n \leq 10^3$
• 对于 $100\%$的数据，$1 \leq k \leq n \leq 2 \times 10^5$