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 REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

vector<pair<int,int>> make_seica(string str){
	vector<pair<int,int>> ret;
	if(str[0] == '0')ret.EB(1,0);
	else ret.EB(0,0);
	REP(i,str.size()-1){
		if(str[i] != str[i+1])ret.EB(str[i] - '0',i+1);
	}
	if(str[str.size() - 1] == '0')ret.EB(0,str.size());
	else ret.EB(1,str.size());
	
	while(ret.size() < 5005)ret.EB(1-ret.back().FI,str.size());
	
	return ret;
}

int solve_seica(vector<pair<int,int>> a, vector<pair<int,int>> b){
	int ret = INF;
	REP(i,a.size()){
		int now = 0;
		if(a[i].FI != b[b.size() - 1].FI)continue;
		REV(j,b.size()){
			int tmp = i - ((int)b.size() - 1 - j);
		//	cout << tmp << " " << j << endl;
			if(tmp >= 0){
				now += (abs(a[tmp].SE - b[j].SE));
			}
			else{
				now += b[j].SE;
			}
		}
		//cout << "      " << i << " " << now << endl;
		ret = min(ret, now);
	}
	return ret;
}

int main(){
	
	int n;cin >> n;
	string s,t;cin >> s >> t;
	auto a = make_seica(s);
	auto b = make_seica(t);
		
	cout << min(solve_seica(a,b),solve_seica(b,a)) << endl;
	
	return 0;
}
