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 il inline
#define vd void
typedef long long ll;
il ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
char s[5010],t[5010];
int n,A[5010],B[5010],a,b,SA[5010],SB[5010];
il int S(int*s,int l,int r,int k=0){
	if(l>r)return 0;
	return k?s[r]-s[l-1]:(r-l+1)*n-s[r]+s[l-1];
}
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	n=gi();scanf("%s",s+1);scanf("%s",t+1);
	int ans=INT_MAX;
	A[++a]=0,B[++b]=0;
	if(s[1]=='1')A[++a]=0;if(t[1]=='1')B[++b]=0;
	for(int i=1;i<n;++i)if(s[i]!=s[i+1])A[++a]=i;
	for(int i=1;i<n;++i)if(t[i]!=t[i+1])B[++b]=i;
	A[++a]=n,B[++b]=n;
	if(s[n]=='1')A[++a]=n;if(t[n]=='1')B[++b]=n;
	for(int i=1;i<=a;++i)SA[i]=SA[i-1]+A[i];
	for(int i=1;i<=b;++i)SB[i]=SB[i-1]+B[i];
	for(int i=1;i<=b;i+=2){
		int c=std::min(b,a+i-1),res=S(SB,1,i-1,1)+S(SB,i+a,b)+S(SA,c-i+2,a);
		for(int j=i;j<=c;++j)res+=abs(A[j-i+1]-B[j]);
		ans=std::min(res,ans);
	}
	for(int i=1;i<=a;i+=2){
		int c=std::min(a,b+i-1),res=S(SA,1,i-1,1)+S(SA,i+b,a)+S(SB,c-i+2,b);
		for(int j=i;j<=c;++j)res+=abs(B[j-i+1]-A[j]);
		ans=std::min(res,ans);
	}
	return printf("%d\n",ans),0;
}
