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<deque>
#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/
const int N=5050;

int n;
char s[N],t[N];

deque<int> A,B;

int main(){
    scanf("%d",&n);
    scanf("%s",s+1);
    scanf("%s",t+1);
    FOR(i,1,n)s[i]-='0',t[i]-='0';

    s[0]=!s[1],t[0]=!t[1];
    s[n+1]=!s[n],t[n+1]=!t[n];

    FOR(i,1,n+1)if(s[i-1]!=s[i])A.push_back(i);
    FOR(i,1,n+1)if(t[i-1]!=t[i])B.push_back(i);
    if(s[1]!=t[1])A.push_front(1);
    for(int i=0;i<=n+1;i+=1)A.push_front(1),A.push_front(1);
    for(int i=0;i<=n+1;i+=1)A.push_back(n+1),A.push_back(n+1);
    //for(int i=0;i<A.size();i++)printf("%d ",A[i]); puts("");
    //for(int i=0;i<B.size();i++)printf("%d ",B[i]); puts("");
    int ans=1e9;
    for(int i=0;i+B.size()<=A.size();i+=2){
        int tot=0;
        for(int j=0;j<i;j++)tot+=abs(A[j]-1);//全放左边
        for(int j=0;j<B.size();j++){
            tot+=abs(A[i+j]-B[j]);
        }
        for(int j=i+B.size();j<A.size();j++)tot+=abs(A[j]-(n+1));//全放右边
        ans=min(ans,tot);
    }
    printf("%d\n",ans);
    return 0;
}
