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;
using ull = uint64_t;
using ll = int64_t;
using ld = long double;

const int N = 30228;

int a[N], b[N];
int ac, bc;

int l[N];
int r[N];

int main() {
#ifdef BZ
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20);
    int n;
    string s, t;
    cin >> n >> s >> t;
    for (int i = 1; i < n; ++i) {
        if (s[i] != s[i - 1]) {
            a[ac++] = i;
        }

        if (t[i] != t[i - 1]) {
            b[bc++] = i;
        }
    }

    int ans = N * N;

    bool eq = s[0] == t[0];
    for (int i = -n - 1; i <= n + 1; ++i) {
        if ((i % 2 == 0) != eq) {
            continue;
        }

        int lc = 0, rc = 0;

        if (i > 0) {
            fill(l, l + i, 0);
            lc = i;
        } else {
            fill(r, r + (-i), 0);
            rc = -i;
        }

        copy(a, a + ac, l + lc);
        copy(b, b + bc, r + rc);
        lc += ac;
        rc += bc;
        while (lc < rc) {
            l[lc++] = n;
        }

        while (rc < lc) {
            r[rc++] = n;
        }

        int cur = 0;
        for (int j = 0; j < lc; ++j) {
            cur += abs(l[j] - r[j]);
        }

        ans = min(ans, cur);
    }

    cout << ans << "\n";
}

