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 N = 5010;

int A[N], B[N]; char s[N];

inline void process(int t[], int n) {
    t[1] = s[1] == '1';
    for (int i = 2; i <= n; i++) t[i] = s[i] != s[i - 1];
}

int main() {
    int n; scanf("%d", &n);
    scanf("%s", s + 1), process(A, n), scanf("%s", s + 1), process(B, n);
    int ct = 0, ct1 = 0, res = 1e9;
    vector<int> wkr, zjk;
    for (int i = 1; i <= n; i++) {
        if (B[i]) wkr.push_back(i), ct1++;
        if (A[i]) zjk.push_back(i), ct++;
    }
    for (int t = -ct / 2 * 2; t <= ct1; t += 2) {
        int tp = 0, tmp = 0, tp1 = 0;
        for (int i = 1; i <= t; i++) tmp += wkr[tp++] - 1;
        for (int i = 1; i <= -t; i++) tmp += zjk[tp1++] - 1;
        for (int i = tp; i < wkr.size(); i++) {
            if (tp1 >= zjk.size()) tmp += n + 1 - wkr[tp++];
            else tmp += abs(wkr[tp++] - zjk[tp1++]);
        }
        for (int i = tp1; i < zjk.size(); i++) tmp += n + 1 - zjk[tp1++];
        res = min(res, tmp);
    }
    
    printf("%d\n", res);
}