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;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n;
string a,b;
vector<int>va,vb;
int main(){
	cin>>n;
	cin>>a>>b;
	char ch; int len;
	for(int i=0;i<a.size();i++){
		if(i == 0){
			ch = a[i];
			len = 1;
		}
		else if(ch == a[i]) len++;
		else{
			va.pb(len);
			ch = a[i];
			len = 1;
		}
	}
	va.pb(len);
	
	for(int i=0;i<b.size();i++){
		if(i == 0){
			ch = b[i];
			len = 1;
		}
		else if(ch == b[i]) len++;
		else{
			vb.pb(len);
			ch = b[i];
			len = 1;
		}
	}
	vb.pb(len);
	//cout<<va.size()<<" "<<vb.size()<<endl;
	int ans = INF;
	int sz = va.size();
	int sz2 = vb.size();
	for(int i=-sz;i<=sz2;i++){
		int fl = (i%2+2)%2;
		if((a[0]!=b[0])+fl == 1) continue;
		//cout<<i<<endl;
		//0..0(i個) va
		//vb
		vector<int>posa,posb;
		for(int ii=0;ii<va.size();ii++){
			rep(j,va[ii]) posa.pb(i+ii);
		}
		for(int ii=0;ii<vb.size();ii++){
			rep(j,vb[ii]) posb.pb(ii);
		}
		int x = 0;
		for(int i=0;i<posa.size();i++) x += abs(posa[i]-posb[i]);
		ans = min(ans,x);
	}
	cout<<ans<<endl;
}