Cow Dance Transformation

Farmer John has choreographed a dance for a line of \(N\) cows (where \(2 \le N \le 10^6\)). In the dance, each move consists of two cows swapping positions, but they can only swap if they are at most \(K\) positions apart (with \(1 \le K < N\)).

The cows are of two types: Guernsey and Holstein, represented by the characters 0 and 1 respectively. Thus, each state of the dance is recorded as a binary string of length \(N\). Unfortunately, an adversary has erased all of the intermediate dance states, leaving only the first and the last binary strings. Now, with a major competition looming, Farmer John must reconstruct the dance.

Your task is to compute the minimum number of moves required to transform the initial arrangement into the target arrangement using the allowed moves. Note that in each move, two cows at positions \(i\) and \(j\) may swap if and only if \(|i - j| \le K\) (here \(|i - j|\) denotes the absolute difference between positions). If a cow must move a distance \(d\) and each move can cover at most \(K\) positions, then the cost for that cow is \(\lceil d/K \rceil\). The optimal strategy is to pair mismatched positions in order and sum their individual move counts.

More formally, let the initial and target states be represented by strings \(s\) and \(t\) respectively. Define:

[ A = {i \mid s_i = 0 \text{ and } t_i = 1}, \quad B = {i \mid s_i = 1 \text{ and } t_i = 0}. ]

Assuming \(|A| = |B|\) (which is necessary for the transformation to be possible), pair the \(i\)th element of \(A\) with the \(i\)th element of \(B\) (when both sets are sorted in increasing order). The answer is then:

[ \text{Answer} = \sum_{i=1}^{|A|} \left\lceil \frac{|A_i - B_i|}{K} \right\rceil. ]

inputFormat

The first line contains two integers \(N\) and \(K\) separated by a space, where \(2 \le N \le 10^6\) and \(1 \le K < N\). The second line contains a binary string of length \(N\) representing the initial arrangement. The third line contains another binary string of length \(N\) representing the target arrangement.

outputFormat

Output a single integer: the minimum number of moves required to transform the initial arrangement into the target arrangement using the allowed swaps.

sample

5 2
01011
01101

1