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<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=3*5005;
char s[maxn],t[maxn];
vi marks,markt;
int a[maxn],b[maxn];
int main(){
    int n;scanf("%d%s%s",&n,s+1,t+1);
    if(s[1]=='1')marks.pb(0);
    rep(i,1,n-1)if(s[i]!=s[i+1])marks.pb(i);
    if(s[n]=='1')marks.pb(n);
    if(t[1]=='1')markt.pb(0);
    rep(i,1,n-1)if(t[i]!=t[i+1])markt.pb(i);
    if(t[n]=='1')markt.pb(n);
    int cnts=marks.size(),cntt=markt.size(),add=cntt-cnts;
    int ans=1e9+100;
    rep(i,1,cnts)a[i+cntt]=marks[i-1];
    rep(i,1,cntt)a[i+cnts+cntt]=n;
    for(int i=0;i<=cnts+cntt;i+=2){
        int tmp=0;
        rep(j,1,i)b[j]=0;
        //cout<<markt[0]<<endl;
        rep(j,1,cntt)
        b[i+j]=markt[j-1];
        rep(j,1,cnts+cntt-i)b[j+i+cntt]=n;
        rep(j,1,cnts+cntt*2)tmp+=abs(a[j]-b[j]);
        ans=min(ans,tmp);
    }
 /*   rep(i,-cnts,cnts+add){//从开头通过的
        int tmp=0;
        int but=add-i;//从结尾通过的
        if(i<0){
            rep(j,1,-i)tmp+=abs(s[i-1]-0);
            rep(j,-i+1,cnts)tmp+=abs(s[i-1]-t[j+i-1]);
            rep(j,cnts+i+1,cnts)tmp+=abs(n-t[j-1]);
        }
        else{
            rep(j,cnts+but+1,cnts)tmp+=abs(s[i-1]-n);
            for(int j=cnts+but;j>=i;j--)tmp+=abs(s[i-1]-t[i-1]);
            rep(j,1,i)tmp+=t[i];
        }
        ans=min(ans,tmp);
        cout<<tmp<<endl;
    }*/
    cout<<ans;
    return 0;
}