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;

#define N 5200

int n,ans,a[N],b[N];
char s[N],t[N];

void solve(char s[],char t[]){
	memset(a,0,sizeof a); memset(b,0,sizeof b);
	for (int i=1;i<n;++i){
		if (s[i]=='0'&&s[i+1]=='1') a[i]=-1;
		if (s[i]=='1'&&s[i+1]=='0') a[i]=1;
		if (t[i]=='0'&&t[i+1]=='1') b[i]=-1;
		if (t[i]=='1'&&t[i+1]=='0') b[i]=1;
	}
	for (int k=1;k<=n;++k){
		int sum=0;
		for (int i=1;i<k;++i) if (b[i]) sum+=i;
		int i=1,j=k;
		for (;i<n;++i) if (a[i]){
			for (;j<n&&b[j]!=a[i];++j)
				if (b[j]) sum+=j;
			sum+=abs(i-j);
			j+=j<n;
		}
		for (;j<n;++j) if (b[j]) sum+=n-j;
		ans=min(ans,sum);
	}
}

int main(){
	scanf("%d%s%s",&n,s+1,t+1);
	if (n<=2){
		for (int i=1;i<=n;++i) ans+=s[i]!=t[i];
		printf("%d\n",ans);
		return 0;
	}
	ans=n*n;
	solve(s,t); solve(t,s);
	reverse(s+1,s+n+1); reverse(t+1,t+n+1);
	solve(s,t); solve(t,s);
	printf("%d\n",ans);
	
	return 0;
}
			