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 <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

int n;

char S[5555], T[5555];

vector <ll> VS(0), VT(0);

ll Abs(ll x) {return x < 0 ? -x : x;}

int main() {
    scanf("%d%s%s", &n, S + 1, T + 1);
    for(int i = 2; i <= n; i++) if(S[i] == S[i - 1]) VS.push_back(i);
    for(int i = 2; i <= n; i++) if(T[i] == T[i - 1]) VT.push_back(i);
    int szS = VS.size(), szT = VT.size();
    ll ans = 2e18;
    for(int i = -szT; i <= szS; i++) {
        ll nw = 0, o = 0;
        for(int j = 0; j < szT; j++) {
            int x = i + j;
            if(x < 0) nw += Abs((VT[j] - 1)), o ^= 1;
            else if(x >= szS) nw += Abs(n + 1 - VT[j]);
            else nw += Abs(VS[x] - VT[j]);
        }
        for(int j = 0; j < i; j++) nw += VS[j] - 1, o ^= 1;
        for(int j = i + szT; j < szS; j++) nw += n + 1 - VS[j];
        if(o ^ (S[1] - '0') ^ (T[1] - '0') ^ 1) ans = min(ans, nw);
        else ans = min(ans, nw + n);
    }
    printf("%lld\n", ans);
    return 0;
}