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 int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N;
string S,T;

signed main(){
    cin>>N>>S>>T;

    if(N==1){
        if(S==T)cout<<0<<endl;
        else cout<<1<<endl;
        return 0;
    }

    vint A,B;
    rep(i,N-1){
        if(S[i+1]==S[i])A.pb(i);
        if(T[i+1]==T[i])B.pb(i);
    }


    int ans=LLONG_MAX;

    rep(uku,2){
        for(int d=0;d<=N;d++){
            if((S[0]-'0'+d)%2!=(T[0]-'0'))continue;
            int cost=0;
            rep(i,d){
                if(i<B.size())cost+=B[i]+1;
                else cost+=N-2+1+1;
            }
            rep(i,A.size()){
                if(i+d<B.size())cost+=abs(A[i]-B[i+d]);
                else cost+=N-2-A[i]+1;
            }
            for(int i=d+A.size();i<B.size();i++)cost+=N-2-B[i]+1;
            chmin(ans,cost);
        }
        swap(A,B);
    }




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