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 forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << (a) << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int N = 5050;

int n, odd, da[N], db[N], za, zb;
string a,b;

int get(const vi &p, int i) { return i < 0 ? -1 : i < si(p) ? p[i] : n-1; }

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

    cin >> n >> a >> b;
    odd = a[0] != b[0];
    vi pa,pb;
    forn(i,n-1) if (a[i] == a[i+1]) pa.pb(i);
    forn(i,n-1) if (b[i] == b[i+1]) pb.pb(i);
    if (si(pa) < si(pb)) swap(pa,pb);

    int ans = 1e9;
    for (int left = -n; left <= n; left++) if ((odd + left)%2 == 0) {
        int cand = 0;
        for (int i = -n; i < 2*n; i++) {
            int pi = get(pa,i), pj = get(pb,i+left);
            cand += abs(pi-pj);
        }
        ans = min(ans, cand);
    }
    cout << ans << endl;

    return 0;
}
