You are given strings s and t, both of length N. s and t consist of `0` and `1`. Additionally, in these strings, the same character never occurs three or more times in a row.

You can modify s by repeatedly performing the following operation:

* Choose an index i (1 \leq i \leq N) freely and invert the i-th character in s (that is, replace `0` with `1`, and `1` with `0`), under the condition that the same character would not occur three or more times in a row in s after the operation.



Your objective is to make s equal to t. Find the minimum number of operations required.

Constraints

* 1 \leq N \leq 5000
* The lengths of s and t are both N.
* s and t consists of `0` and `1`.
* In s and t, the same character never occurs three or more times in a row.

Input

Input is given from Standard Input in the following format:


N
s
t


Output

Find the minimum number of operations required to make s equal to t. It can be proved that the objective is always achievable in a finite number of operations.

Examples

Input

4
0011
0101


Output

4


Input

1
0
0


Output

0


Input

8
00110011
10101010


Output

10
#include <bits/stdc++.h>
using namespace std;

const int MAXN=21111;
int a[MAXN], b[MAXN], f[MAXN], g[MAXN];
int n, m, num1, num2, ans;

int main() {
    scanf("%d", &n);
    for(int i=1;i<=n;++i) {
        scanf("%1d", &a[i]);
        num1+=(i==1 || a[i]!=a[i-1]) ? 1 : 0;
    }
    for(int i=1;i<=n;++i) {
        scanf("%1d", &b[i]);
        num2+=(i==1 || b[i]!=b[i-1]) ? 1 : 0;
    }
    if(num1>num2) {
        for(int i=1;i<=n;++i) {
            swap(a[i], b[i]);
        }
        swap(num1, num2);
    }
    for(int i=1;i<=n;++i) {
        g[++m]=2;
    }
    for(int i=1;i<=n;++i) {
        if(i==1 || b[i]!=b[i-1]) g[++m]=2;
        g[++m]=b[i];
    }
    for(int i=0;i<=n;++i) {
        g[++m]=2;
    }
    ans=1e9;
    for(int i=1;i+num1+n<=m;++i) {
        if(a[1]==b[1] && !((n+i)&1)) continue;
        else if(a[1]!=b[1] && ((n+i)&1)) continue;
        for(int j=1;j<=i;++j) {
            f[j]=2;
        }
        int now=i;
        for(int j=1;j<=n;++j) {
            if(j>1 && a[j]!=a[j-1]) f[++now]=2;
            f[++now]=a[j];
        }
        for(;++now<=m;) {
            f[now]=2;
        }
        int L=1, R=1, res=0;
        // for(int j=1;j<=m;++j) {
        //  printf("%c", f[j]<=1 ? f[j]+'0' : '|');
        // } puts("");
        // for(int j=1;j<=m;++j) {
        //  printf("%c", g[j]<=1 ? g[j]+'0' : '|');
        // } puts("");
        while(L<=m && R<=m) {
            if(f[L]==2 && g[R]==2) {
                res+=abs(L-R);
                ++L;
                ++R;
            }
            while(L<=m && f[L]!=2) ++L;
            while(R<=m && g[R]!=2) ++R;
        }
        // printf("==> %d\n", res);
        ans=min(ans, res);
    }
    printf("%d\n", ans);
    return 0;
}