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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
int solve(bool dif0,V<int> x,V<int> y){
	int N = x.size();
	if(N==0) return dif0?1:0;
	int x0 = 0;
	int y0 = 0;
	V<int> x0s,y0s;
	rep(i,N) if(x[i]==0) x0++,x0s.pb(i);
	rep(i,N) if(y[i]==0) y0++,y0s.pb(i);
	int ans = 1e9;
	for(int l = -x0-1; l<=y0+1; l++){
		int r = y0-x0-l;
		if( (l%2!=0) ^ dif0 ) continue;
		V<int> a,b;
		if(l>0){
			rep(i,l) a.pb(-1);
		}else{
			rep(i,-l) b.pb(-1);
		}
		for(int v:x0s) a.pb(v);
		for(int v:y0s) b.pb(v);
		if(r>0){
			rep(i,r) a.pb(N);
		}else{
			rep(i,-r) b.pb(N);
		}
		assert(a.size() == b.size());
		int cost = 0;
		int K = a.size();
		rep(i,K) cost += abs(a[i]-b[i]);
		chmin(ans,cost);
	}
	return ans;
}
int main(){
	int N;
	string s,t;
	cin>>N>>s>>t;
	bool dif0 = s[0]!=t[0];
	V<int> x(N-1),y(N-1);
	rep(i,N-1){
		x[i] = s[i]!=s[i+1];
		y[i] = t[i]!=t[i+1];
	}
	cout<<solve(dif0,x,y)<<endl;

}