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;
const int N=5010;
char a[N],b[N];
int n,c[N],c1,d[N],d1;
int ty[N],ty2[N],ans;
int abs(int x){
	return x<0?-x:x;
}
int ac(int x){
	return max(1,min(c1,x));
}
int ad(int x){
	return max(1,min(d1,x));
}
int main(){
	cin>>n;
	ans=n*n;
	scanf("%s",a+1);
	scanf("%s",b+1);
	ty[0]=(a[1]-'0')^1;
	c[++c1]=0;
	for (int i=1;i<=n;i++){
		if (a[i]==a[i+1])ty[i]=2;
		else ty[i]=a[i]-'0',c[++c1]=i;
	}
	ty2[0]=(b[1]-'0')^1;
	d[++d1]=0;
	for (int i=1;i<=n;i++){
		if (b[i]==b[i+1])ty2[i]=2;
		else ty2[i]=b[i]-'0',d[++d1]=i;
	}
	for (int i=1;i<=d1;i++){
		int x=d[ad(i)];
		if (ty2[x]==ty[0]){
			int sum=0;
			for (int j=-5002;j<=5002;j++)
				sum+=abs(c[ac(j)]-d[ad(i+j-1)]);
			ans=min(ans,sum);
		}
		if (ty2[x]==ty[n]){
			int sum=0;
			for (int j=5002;j>=-5002;j--)
				sum+=abs(c[ac(j)]-d[ad(i+j-c1)]);
			ans=min(ans,sum);
		}
	}
	for (int i=1;i<=c1;i++){
		int x=c[i];
		if (ty[x]==ty2[0]){
			int sum=0;
			for (int j=-5002;j<=5002;j++)
				sum+=abs(d[ad(j)]-c[ac(i+j-1)]);
			ans=min(ans,sum);
		}
		if (ty[x]==ty2[n]){
			int sum=0;
			for (int j=5002;j>=-5002;j--)
				sum+=abs(d[ad(j)]-c[ac(i+j-d1)]);
			ans=min(ans,sum);
		}
	}
	cout<<ans<<endl;
}