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 "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }


/*
 update : [s,t) に xを加算
 query  : [s,t) の　最大(小)値を出力する
 */

/* [0..N-1] */
const ll INIT = 0; // 問題に合わせる
struct SegTree {
    int N;
    ll init_v;
    vector<ll> node, lazy;
    
    SegTree(int _N):init_v(INIT) {
        N = 1;
        while (N < _N) N *= 2;
        node.resize(2 * N - 1, init_v);
        lazy.resize(2 * N - 1, init_v);
    }
    
    ll merge(ll l,ll r){
        return min(l,r);
    }
    void build(){
        for(int k = N - 2; k >= 0; k--){
            node[k] = merge(node[2*k+1],node[2*k+2]);
        }
    }
    void direct_update(int k,ll v){
        node[k+N-1] = v;
    }
    
    void lazy_evaluate(int l, int r,int k){
        node[k] += lazy[k];
        if(r - l > 1){
            lazy[2 * k + 1] += lazy[k];
            lazy[2 * k + 2] += lazy[k];
        }
        lazy[k] = 0;
    }
    
    /* [a,b) 引数の範囲に注意!! s~tまでを更新→update(s,t+1,~) */
    void update(int a, int b, ll x) { update(a, b, 0, 0, N, x); }
    void update(int a, int b, int k, int l, int r, ll x) {
        lazy_evaluate(l,r,k);
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            lazy[k] += x;
            lazy_evaluate(l,r,k);
        }
        else {
            update(a, b, 2 * k + 1, l, (l + r) / 2, x);
            update(a, b, 2 * k + 2, (l + r) / 2, r, x);
            node[k] = merge(node[2 * k + 1],node[2 * k + 2]);
        }
    }
    
    /* [a,b) 引数の範囲に注意!! */
    ll query(int a, int b) { return query(a, b, 0, 0, N); }
    ll query(int a, int b, int k, int l, int r) {
        lazy_evaluate(l, r, k);
        if (r <= a || b <= l) return LLONG_MAX; // min : LLONG_MAX , max : LLONG_MIN
        if (a <= l && r <= b) {
            return node[k];
        }
        else {
            ll vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
            ll vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
            return merge(vl, vr);
        }
    }
};

int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int n,k; cin >> n >> k;
    string s,t; cin >> s >> t;

    SegTree ST(n+10);
    vector<ll> dp(n+1);
    
    for(int i = 0; i < n;i++){
        ll minv = INF;
        if(s[i] == t[i]){
            minv = dp[i];
        }
        if(i != 0 && t[i-1] != t[i]){
            ST.update(0,i,1);
        }
        ll Q = ST.query(max(0,i+1-k),i+1);
        minv = min(minv,(Q+1)/2+1);
        ST.update(i+1,i+2,2*minv);
        dp[i+1] = minv;
    }
    cout << dp[n] << endl;
    
    return 0;
}