Problem Description

The cows have formed a dance team, and Farmer John is their choreographer! The latest and most spectacular dance features \( N \) cows ( \( 2 \le N \le 10^6 \) ) arranged in a line. Each move in the dance involves two cows, at most \( K \) positions apart ( \( 1 \le K < N \) ), gracefully jumping up and landing in each other's positions.

There are two types of cows in the team—Guernsey and Holstein. Therefore, Farmer John records the dance as a series of length \( N \) 01 strings, where 0 represents a Guernsey and 1 represents a Holstein, with the entire string indicating how the cows are arranged in the line.

Unfortunately, Farmer Nhoj (the choreographer of the opposing team) has deliberately sabotaged the dance and erased all but the first and last 01 strings! With a big competition coming up, Farmer John needs to rebuild the dance in every second he can.

Given these two 01 strings, help Farmer John find the minimum number of moves in the dance!

Input Format

The first line of input contains \( N \) and \( K \).

The second line contains the first 01 string.

The third line contains the last 01 string.

The input guarantees that both 01 strings contain the same number of 1s.

Output Format

Output the minimum number of moves in the dance.

Sample Input and Output

Sample Input #1

4 1
0111
1110

Sample Output #1

3

Sample Input #2

5 2
11000
00011

Sample Output #2

3

Sample Input #3

5 4
11000
00011

Sample Output #3

2

Notes/Hints

Sample Explanation 1

A possible dance sequence:

0111 -> 1011 -> 1101 -> 1110

Sample Explanation 2

A possible dance sequence:

11000 -> 01100 -> 00110 -> 00011

Sample Explanation 3

A possible dance sequence:

11000 -> 10010 -> 00011

Test Case Properties

• Test cases \( 4-5 \): \( K = 1 \).
• Test cases \( 6-7 \): Each string contains at most 8 1s.
• Test cases \( 8-15 \): \( N \le 5000 \).
• Test cases \( 16-23 \): No additional restrictions.

见题面 Input 部分

见题面 Output 部分