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 N 5010
using namespace std;
template <typename T> void read(T &x){
	x=0;char c=getchar();int fh=1;
	while (!isdigit(c)){if (c=='-')fh=-1;c=getchar();}
	while (isdigit(c))x=x*10+c-'0',c=getchar();
	x*=fh;
}
int n,an,bn,na[N],nb[N],a[N],b[N],ansn=1e9;
char ch;
int add(int x,int y){
	int sum=0;
	for (int i=1-x,j=1-y;i<=an||j<=bn;i++,j++){
		if (i<1)sum+=nb[j];
		if (j<1)sum+=na[i];
		if (i>an)sum+=n-nb[j];
		if (j>bn)sum+=n-na[i];
		if (i>=1&&j>=1&&i<=an&&j<=bn)sum+=abs(na[i]-nb[j]);
	}
	return sum;
}
int main(){
	read(n);
	for (int i=1;i<=n;i++){ch=getchar();while (ch!='0'&&ch!='1')ch=getchar();a[i]=ch-'0';}
	for (int i=1;i<=n;i++){ch=getchar();while (ch!='0'&&ch!='1')ch=getchar();b[i]=ch-'0';}
	for (int i=1;i<=n;)if (a[i+1]!=a[i]||i==n){na[++an]=i;i++;}else{na[++an]=i+1;i+=2;}
	for (int i=1;i<=n;)if (b[i+1]!=b[i]||i==n){nb[++bn]=i;i++;}else{nb[++bn]=i+1;i+=2;}
	if (a[1]==b[1]){
		for (int i=0;i<=bn;i+=2)ansn=min(ansn,add(0,i));
		for (int i=0;i<=an;i+=2)ansn=min(ansn,add(i,0));
	}else{
		for (int i=1;i<=bn;i+=2)ansn=min(ansn,add(0,i));
		for (int i=1;i<=an;i+=2)ansn=min(ansn,add(i,0));
	}
	cout<<ansn<<endl;
	return 0;
}