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 ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=5005;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
//inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}int ans=1e9,n,a[MAXN],b[MAXN],cnt1,cnt2;char s1[MAXN],s2[MAXN];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),scanf("%s%s",s1+1,s2+1);
	Rep(i,1,n-1)if(s1[i]!=s1[i+1])a[++cnt1]=i;
	Rep(i,1,n-1)if(s2[i]!=s2[i+1])b[++cnt2]=i;
	Rep(i,-cnt1-1,cnt2+1)if((i&1)^(s1[1]==s2[1])){
		int tmp=0;
		Rep(j,min(1,1-i),max(cnt1,cnt2-i))
			tmp+=abs((j<0?0:j>cnt1?n:a[j])-(i+j<0?0:i+j>cnt2?n:b[i+j]));
		ans=min(ans,tmp);
	}cout<<ans<<'\n';
	return 0;
}


