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<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int h=5000;
char s[5050],t[5050];
int q1[20202],q2[20202];
bool tp1[20202],tp2[20202];
int n;
int jud(int p1,int p2)
{
	int ret=0;
	for(int i=p1,j=p2;q1[i]!=1||q2[j]!=1;i--,j--)
		ret+=abs(q1[i]-q2[j]);
	for(int i=p1+1,j=p2+1;q1[i]!=n+1||q2[j]!=n+1;i++,j++)
		ret+=abs(q1[i]-q2[j]);
	return ret;
}
int main()
{
	int cnt1,cnt2,ans=214748364;
	scanf("%d",&n);
	scanf("%s",s+1);
	scanf("%s",t+1);
	cnt1=cnt2=h;
	for(int i=2;i<=n;i++)
		if(s[i]!=s[i-1])
		{
			q1[++cnt1]=i;
			tp1[cnt1]=s[i]-'0';
		}
	for(int i=2;i<=n;i++)
		if(t[i]!=t[i-1])
		{
			q2[++cnt2]=i;
			tp2[cnt2]=t[i]-'0';
		}
	q1[h]=q2[h]=1;
	tp1[h]=s[1]-'0';
	tp2[h]=t[1]-'0';
	for(int i=h-1;i>=0;i--)
	{
		q1[i]=q2[i]=1;
		tp1[i]=tp1[i+1]^1;
		tp2[i]=tp2[i+1]^1;
	}
	for(int i=cnt1+1;i<=cnt1+h+1;i++)
	{
		q1[i]=n+1;
		tp1[i]=tp1[i-1]^1;
	}
	for(int i=cnt2+1;i<=cnt2+h+1;i++)
	{
		q2[i]=n+1;
		tp2[i]=tp2[i-1]^1;
	}
	for(int i=h+h-cnt1-1;i<=cnt2+1;i++)
		if(tp1[h]==tp2[i])
			ans=min(ans,jud(h,i));
	printf("%d",ans);
	return 0;
}