Black or White

Problem E Black or White

Here lies a row of a number of bricks each painted either black or white. With a single stroke of your brush, you can overpaint a part of the row of bricks at once with either black or white paint. Using white paint, all the black bricks in the painted part become white while originally white bricks remain white; with black paint, white bricks become black and black ones remain black. The number of bricks painted in one stroke, however, is limited because your brush cannot hold too much paint at a time. For each brush stroke, you can paint any part of the row with any number of bricks up to the limit.

In the first case of the sample input, the initial colors of four bricks are black, white, white, and black. You can repaint them to white, black, black, and white with two strokes: the first stroke paints all four bricks white and the second stroke paints two bricks in the middle black.

Your task is to calculate the minimum number of brush strokes needed to change the brick colors as specified. Never mind the cost of the paints.

Input

The input consists of a single test case formatted as follows.

$n$ $k$ $s$ $t$

The first line contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 500 000$). $n$ is the number of bricks in the row and $k$ is the maximum number of bricks painted in a single stroke. The second line contains a string $s$ of $n$ characters, which indicates the initial colors of the bricks. The third line contains another string $t$ of $n$ characters, which indicates the desired colors of the bricks. All the characters in both s and t are either B or W meaning black and white, respectively.

Output

Output the minimum number of brush strokes required to repaint the bricks into the desired colors.

Sample Input 1

4 4 BWWB WBBW

Sample Output 1

2

Sample Input 2

4 3 BWWB WBBW

Sample Output 2

3

Sample Input 3

4 3 BWWW BWWW

Sample Output 3

0

Sample Input 4

7 1 BBWBWBW WBBWWBB

Sample Output 4

4

Example

Input

4 4 BWWB WBBW

Output

2

inputFormat

input, the initial colors of four bricks are black, white, white, and black. You can repaint them to white, black, black, and white with two strokes: the first stroke paints all four bricks white and the second stroke paints two bricks in the middle black.

Your task is to calculate the minimum number of brush strokes needed to change the brick colors as specified. Never mind the cost of the paints.

Input

The input consists of a single test case formatted as follows.

$n$ $k$ $s$ $t$

The first line contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 500 000$). $n$ is the number of bricks in the row and $k$ is the maximum number of bricks painted in a single stroke. The second line contains a string $s$ of $n$ characters, which indicates the initial colors of the bricks. The third line contains another string $t$ of $n$ characters, which indicates the desired colors of the bricks. All the characters in both s and t are either B or W meaning black and white, respectively.

outputFormat

Output

Output the minimum number of brush strokes required to repaint the bricks into the desired colors.

Sample Input 1

4 4 BWWB WBBW

Sample Output 1

2

Sample Input 2

4 3 BWWB WBBW

Sample Output 2

3

Sample Input 3

4 3 BWWW BWWW

Sample Output 3

0

Sample Input 4

7 1 BBWBWBW WBBWWBB

Sample Output 4

4

Example

Input

4 4 BWWB WBBW

Output

2

样例

4 4
BWWB
WBBW

2