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 = 500005, inf = 1 << 30;

#define mp make_pair
#define x first 
#define y second 
pair<int, int> a[maxn], b[maxn];
char s[maxn], t[maxn];

int n, ans = inf, c, d;

inline void chkmin(int &a, int b) {if (a > b) a = b;}

void solve()
{
	for (int i = 0; i <= n; ++i) {
        if ((a[1].y + b[1].y + i) & 1) continue;
        int res = 0, now = 1;
        while (now <= c) { 
            int ps = a[now].x, pt = now + i <= d ? b[now + i].x : n + 1;
            res += abs(pt - ps), ++ now;
        }
        while (now + i <= d) res += n + 1 - b[now + i].x, ++ now;
        for (int j = 1; j <= i; ++j) {
            int pt = j <= d ? b[j].x : n + 1; 
            res += pt - 1; 
        }
        chkmin(ans, res);
    }
}

int main()
{
    scanf("%d%s%s", &n, s + 1, t + 1);

    for (int i = 1; i <= n; ++i) { 
        if (s[i] != s[i - 1]) a[++c] = mp(i, s[i] ^ 48);
        if (t[i] != t[i - 1]) b[++d] = mp(i, t[i] ^ 48);
    }
    solve(), swap(c, d), swap(a, b), solve();
	
    printf("%d\n", ans);
	
    return 0;
}

