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<cstdio>
using namespace std;
#define N 15005
int a[N],b[N],n,s1,s2;
char s[N],t[N];
long long solve(int t)
{
	long long as=0;
	int fg=0;
	if(t<0){t=-t;fg=1;for(int i=1;i<=n;i++)a[i]^=b[i]^=a[i]^=b[i];s1^=s2^=s1^=s2;}
	int l1=1,r1=1-t;
	while(1)
	{
		int tp1=a[l1],tp2=r1<0?0:b[r1];
		if(l1>s1)tp1=n;if(r1>s2)tp2=n;
		as+=tp1<tp2?tp2-tp1:tp1-tp2;
		if(tp1==tp2&&tp1==n)break;
		l1++,r1++;
	}
	if(fg){for(int i=1;i<=n;i++)a[i]^=b[i]^=a[i]^=b[i];s1^=s2^=s1^=s2;}
	return as;
}
int main()
{
	scanf("%d%s%s",&n,s+1,t+1);
	for(int i=1;i<=n;i++)if(s[i]!=s[i+1])a[++s1]=i;
	for(int i=1;i<=n;i++)if(t[i]!=t[i+1])b[++s2]=i;
	solve(-1);
	long long mn=1e18;for(int i=s[1]==t[1]?-5000:-5001;i<=5000;i+=2){long long tp=solve(i);if(tp<mn)mn=tp;}
	printf("%lld\n",mn);
}