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 <utility>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <list>

#define MAX_N 105

using namespace std;
typedef long long ll;

int main() {
    int N;
    int ans = -1;
    string s,t;
    cin>>N;
    cin>>s;
    cin>>t;
    list<int> s_,t_;
    s_.push_back(0);
    t_.push_back(0);
    for(int i = 0;i < N-1;i++){
        if(s[i]!=s[i+1]){
            s_.push_back(i+1);
        }
        if(t[i]!=t[i+1]){
            t_.push_back(i+1);
        }
    }
    s_.push_back(N);
    t_.push_back(N);
    if(s_.size()>t_.size()){
        swap(s_,t_);
    }
    if(s[0]!=t[0]){
        t_.push_front(0);
    }
    int count = ((t_.size()+1)/2)*2;
    for(int c = 0;c<count;c++){
        s_.push_front(0);
    }
    list<int>::iterator it1=s_.begin(),it2=t_.begin();
    while(t_.size()!=s_.size()){
        t_.push_back(N);
    }
//    for(int x=0;x<t_.size();x++){
//        cout<<*it1<<" "<<*it2<<endl;
//        it1++,it2++;
//    }
    
    while(1){
        int ans_ = 0;
        it1=s_.begin(),it2=t_.begin();
        while(it1!=s_.end()&&!(*it1==N&&*it2==N)){
            ans_ += abs((*it1)-(*it2));
            it1++;
            it2++;
        }
        if(ans>=0){
            ans = min(ans,ans_);
        }else{ans = ans_;}
        
        it1 = s_.begin();
        if(*it1==0&&(++it1)!=s_.end()&&*it1==0) {
            s_.erase(it1);
            s_.erase(s_.begin());
            s_.push_back(N);
            s_.push_back(N);
        }else{
            it2=t_.end();
            it2--,it2--;
            if(*it2==N&&++it2!=t_.end()&&*it2==N){
                t_.erase(it2);
                it2=t_.end();
                it2--;
                t_.erase(it2);
                t_.push_front(0);
                t_.push_front(0);
            }else{
                break;
            }
        }
    }
    cout<<ans<<endl;
}
