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 vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
const int N=15010;

int gi() {
	int x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n,ans=1e9,cs,ct,tt;
char s[N],t[N];
pii ps[N],pt[N],tmp[N];

int main() {
	cin>>n;
	scanf("%s%s",s+1,t+1);
	if(n<=2) {
		int ans=0;
		for(int i=1;i<=n;i++) ans+=s[i]!=t[i];
		cout<<ans;return 0;
	}
	for(int i=1;i<n;i++) {
		if(t[i]=='0'&&t[i+1]=='1') pt[++ct]=mp(0,i);
		if(t[i]=='1'&&t[i+1]=='0') pt[++ct]=mp(1,i);
	}
	int fst=-1,lst;
	for(int i=1;i<n;i++) {
		if(s[i]=='0'&&s[i+1]=='1') {
			ps[++cs]=mp(0,i);
			if(!~fst) fst=0;
			lst=0;
		}
		if(s[i]=='1'&&s[i+1]=='0') {
			ps[++cs]=mp(1,i);
			if(!~fst) fst=1;
			lst=1;
		}
	}
	for(int i=1;i<=ct;i++) fst^=1,tmp[++tt]=mp(fst,0);
	reverse(tmp+1,tmp+tt+1);
	for(int i=1;i<=cs;i++) tmp[++tt]=ps[i];
	for(int i=1;i<=ct;i++) lst^=1,tmp[++tt]=mp(lst,n);
	cs=tt;for(int i=1;i<=cs;i++) ps[i]=tmp[i];
	/*for(int i=1;i<=cs;i++)
		cerr<<ps[i].fi<<' '<<ps[i].se<<'\n';
	cerr<<'\n';
	for(int i=1;i<=ct;i++)
	cerr<<pt[i].fi<<' '<<pt[i].se<<'\n';*/
	for(int i=1;i<=cs-ct+1;i++) {
		if(ps[i].fi!=pt[1].fi) continue;
		int sum=0;
		for(int j=1;j<=cs;j++) {
			int goal;
			if(j<i) goal=0;
			else if(j>=i+ct) goal=n;
			else goal=pt[j-i+1].se;
			//cerr<<i<<' '<<j<<' '<<goal<<'\n';
			sum+=abs(ps[j].se-goal);
			if(sum>=ans) break;
		}
		//cerr<<i<<' '<<sum<<'\n';
		ans=min(ans,sum);
	}
	cout<<ans;
	return 0;
}
