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 INF (int)1e9
int N;
char s[5050],t[5050];
vector<int> sa, ta;
int ans = 0;
int main(){
    scanf("%d%s%s", &N, s, t);

    if(N<3){
        ans = 0;
        for (int i = 0; i < N;i++){
            ans+=s[i] != t[i] ? 1 : 0;
        }
        printf("%d",ans);
        return 0;
    }


    char sss = s[0],ttt=t[0];
    if(s[0]!=t[0]){
        sa.push_back(0);
    }
    for (int i = 1; i < N;i++)
    {
        if(sss!=s[i]){
            sa.push_back(i);
            sss = s[i];
        }
        if(ttt!=t[i]){
            ta.push_back(i);
            ttt = t[i];
        }
    }
    /*
    for (int i = 0; i < sa.size();i++){
        printf("%d ", sa[i]);
    }
    printf("\n");
    for (int i = 0;i<ta.size();i++){
        printf("%d ", ta[i]);
    }
    printf("\n");
*/
    ans = INF;
    for (int i = 0; i < sa.size(); i += 2)
    {
        int ct = 0;
        for (int j = 0; j < i; j++)
        {
            ct += sa[j];
        }
        for (int j = i; j < sa.size() && j - i < ta.size(); j++)
        {
            ct +=abs(sa[j] - ta[j - i]);
        }
        for (int j = sa.size(); j - i < ta.size(); j++)
        {
            ct += N - ta[j - i];
        }
        for (int j = ta.size() + i; j < sa.size(); j++)
        {
            ct += N - sa[j];
        }
        //printf("%d,%d\n", i, ct);
        if(ct<ans){
            ans = ct;
        }
    }
    for (int i = 0; i < ta.size(); i += 2)
    {
        int ct = 0;
        for (int j = 0; j < i; j++)
        {
            ct += ta[j];
        }
        for (int j = i; j < ta.size() && j - i < sa.size(); j++)
        {
            ct +=abs(ta[j] - sa[j - i]);
        }
        for (int j = ta.size(); j - i < sa.size(); j++)
        {
            ct += N - sa[j - i];
        }
        for (int j = sa.size() + i; j < ta.size(); j++)
        {
            ct += N - ta[j];
        }
        if(ct<ans){
            ans = ct;
        }
        //printf("%d,%d\n", i, ct);
    }
    printf("%d", ans);
}