Black or White

A row of $n$ bricks stands in front of you, each brick painted either black or white. One stroke of the brush repaints a contiguous part of the row in a single color. White paint turns every brick in the painted part white, and black paint turns every brick in the painted part black. The brush holds only so much paint at a time, so one stroke covers at most $k$ consecutive bricks. Within that limit you may start a stroke anywhere in the row and use either color.

For example, take four bricks colored black, white, white, black, and suppose you want them to end up white, black, black, white. With $k = 4$ two strokes are enough. Paint all four bricks white, then paint the middle two black.

Compute the minimum number of strokes needed to turn the initial row into the desired row. The cost of the paint does not matter.

The input consists of a single test case in the following format.

n k
s
t

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 500\,000$). $n$ is the number of bricks in the row, and $k$ is the largest number of bricks one stroke paints. The second line contains a string $s$ of $n$ characters giving the initial colors. The third line contains a string $t$ of $n$ characters giving the desired colors. Every character of $s$ and $t$ is either B for black or W for white.

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