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;

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define all(x) (x).begin(), (x).end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N;
    string s, t;
    cin >> N >> s >> t;

    if (N <= 2) {
        int ans = 0;
        for (int i = 0; i < N; i++)
            ans += s[i] != t[i];
        cout << ans << endl;
        return 0;
    }

    vi a, b;

    for (int i = 1; i < N; i++) {
        if (s[i] != s[i-1]) a.push_back(i);
        if (t[i] != t[i-1]) b.push_back(i);
    }

    int ans = INT_MAX;

    int range = a.size();
    bool par = s[0] != t[0];
    if ((range&1) != par)
        range++;

    for (int off = -range; off <= range; off += 2) {
        int pos = 0;

        for (int i = 0; i < a.size(); i++) {
            int tar;
            if (i + off < 0) tar = 0;
            else if (i + off >= b.size()) tar = N;
            else tar = b[i + off];
            pos += abs(a[i] - tar);
        }

        for (int i = 0; i < b.size(); i++) {
            if (i - off < 0) pos += abs(b[i]);
            else if (i - off >= a.size()) pos += abs(b[i] - N);
        }

        ans = min(ans, pos);
    }

    cout << ans << endl;
    return 0;
}

