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;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  string s,t;
  cin>>n>>s>>t;
  {
    string x(s),y(t);
    x.erase(unique(x.begin(),x.end()),x.end());
    y.erase(unique(y.begin(),y.end()),y.end());
    if(x.size()>y.size()) swap(s,t);
  }
  const Int MAX = 5050;
  Int ans=1e9;

  using D = deque<Int>;
  auto gen=
    [&](string x){
      D res;
      char lst='$';
      for(char c:x){
        if(res.empty()||lst!=c) res.emplace_back(0);
        res.back()++;
        lst=c;
      }
      return res;
    };
  
  auto solve=
    [&]()->void{
      D v2=gen(t);
      
      for(Int i=0;i<MAX;i++){        
        D v1=gen(s);        
        Int res=0;
        
        Int posL=0,posR1=v1.size()-1,posR2=posR1;
        auto incL=
          [&](){
            chmin(posL,(Int)v1.size()-1);
            while(posL<(Int)v1.size()&&v1[posL]!=2) posL++;
            if(posL<(Int)v1.size()){
              v1[posL]=1;
              v1.emplace_front(1);
              res+=posL+1;
              posR1++;
              posR2++;
            }else{
              res+=posL;
            }   
          };
        
        auto incR=
          [&](){
            chmin(posR1,(Int)v1.size()-1);
            while(posR1>=0&&v1[posR1]!=2) posR1--;
            assert(posR1>=0);
            
            v1[posR1]=1;
            res+=v1.size()-posR1;
            v1.emplace_back(1);
          };
        auto decR=
          [&](){
            chmin(posR2,(Int)v1.size()-1);
            while(posR2>=0&&v1[posR2]!=1) posR2--;
            Int posR3=posR2-1;
            while(posR3>=0&&v1[posR3]!=1) posR3--;                        
            assert(posR3>=0);
            res+=v1.size()-(posR2+1);
            res+=v1.size()-(posR3+2);
            res+=1;
            v1[posR2]=v1[posR3]=2;
            v1.pop_back();            
          };
        
        if(s[0]!=t[0]) incL();
        for(Int j=0;j<i;j++){
          incL();incL();
        }
        //cout<<i<<":"<<v1.size()<<" "<<v2.size()<<endl;
        
        while(v1.size()<v2.size()) incR();
        while(v1.size()>v2.size()) decR();
        //cout<<i<<":"<<v1.size()<<" "<<v2.size()<<endl;

        Int a=0,b=0;
        for(Int i=0;i<(Int)v1.size();i++){
          a+=v1[i];
          b+=v2[i];
          res+=abs(a-b);
        }
        //cout<<i<<":"<<res<<endl;
        chmin(ans,res);
      }   
    };

  for(Int uku=0;uku<2;uku++){
    solve();
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
  }  
  cout<<ans<<endl;
  return 0;
}
