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<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define rt register int
#define l putchar('\n')
#define ll long long
#define r read()
using namespace std;
inline ll read(){
    ll x=0;char zf=1;char ch=getchar();
    while(ch!='-'&&!isdigit(ch))ch=getchar();
    if(ch=='-')zf=-1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*zf;
}
void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,ans,ret;
int a[100010],b[100010],t1,t2;
char c[100010],s[100010];
int calc(){	
	t1=t2=0;
	for(rt i=1;i<=n;i++)b[++t2]=0;
	for(rt i=1;i<n;i++)if(c[i]=='0'&&c[i+1]=='1')a[++t1]=i;
	for(rt i=1;i<n;i++)if(s[i]=='0'&&s[i+1]=='1')b[++t2]=i;
	for(rt i=1;i<=n;i++)b[++t2]=n;int nowmin=998244353;
	for(rt i=1;i<=t2-n+1;i++){
		int ans=0;
		for(rt j=1;j<i;j++)if(b[j])ans+=b[j];
		for(rt j=0;j<t1;j++)ans+=abs(a[j+1]-b[i+j]);
		for(rt j=t1;b[i+j]!=n;j++)ans+=n-b[i+j];
		nowmin=min(nowmin,ans);
	}
	return nowmin;
}
int main(){
	n=r;
	scanf("%s",c+1);scanf("%s",s+1);
	if(n==1&&c[1]!=s[1])writeln(1);
	else if(n==2&&c[1]!=s[1]&&c[1]==c[2]&&s[1]==s[2])writeln(2);
	else {
		ret=calc();
		for(rt i=1;i<=n;i++)c[i]='0'+'1'-c[i],s[i]='0'+'1'-s[i];
		ret+=calc();cout<<ret;		
	}
	return 0;
}
