Problem: 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

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 2147483647

int N;
int* table;

void init(int first_N){
	while(N < first_N)N *= 2;
}

void update(int loc,int value){
	loc += N-1;

	table[loc] = value;

	if(N == 1)return;

	int parent = (loc-1)/2;

	while(true){
		table[parent] = min(table[2*parent+1],table[2*parent+2]);

		if(parent == 0)break;
		else{
			parent = (parent-1)/2;
		}
	}
}


int query(int search_left,int search_right,int node_id,int node_left,int node_right){

	if(search_right < node_left || search_left > node_right)return NUM;

	if(search_left <= node_left && search_right >= node_right){
		return table[node_id];
	}

	int left_min = query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
	int right_min = query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);

	return min(left_min,right_min);
}

char start[500001],goal[500001];

int main(){

	int first_N,K;
	scanf("%d %d",&first_N,&K);

	N = 1;
	init(first_N+1);

	table = new int[2*N-1];

	for(int i = 0; i <= 2*N-2; i++)table[i] = NUM;

	scanf("%s",start);
	scanf("%s",goal);

	int* change_ruisekiwa = new int[first_N+1];

	change_ruisekiwa[0] = 0;
	for(int i = 0; i < first_N; i++){
		if(goal[i] == goal[i+1]){
			change_ruisekiwa[i+1] = change_ruisekiwa[i];
		}else{
			change_ruisekiwa[i+1] = change_ruisekiwa[i]+1;
		}
	}

	int* dp = new int[first_N+1];

	dp[0] = 0;
	update(0,0);

	for(int i = 1; i <= first_N; i++){
		if(start[i-1] == goal[i-1]){
			dp[i] = dp[i-1];

		}else{

			dp[i] = (query(max(0,i-K),i-1,0,0,N-1)+change_ruisekiwa[i-1]+3)/2;
		}
		update(i,2*dp[i]-change_ruisekiwa[i]);
	}

	printf("%d\n",dp[first_N]);

	return 0;
}