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<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
struct Val{
	int pos,kind;
	Val(int p=0,int k=0)
	{
		pos=p;
		kind=k;
	}
}S[5010],T[5010];
int cnts,cntt;
char s[5010],t[5010];
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s",s+1);
	scanf("%s",t+1);
	cnts=cntt=1;
	if(s[1]=='0')S[1]=Val(0,1);
	else S[1]=Val(0,0);
	if(t[1]=='0')T[1]=Val(0,1);
	else T[1]=Val(0,0);
	for(int i=1;i<=n;i++)
	{
		if(s[i]!=s[i+1])
			S[++cnts]=Val(i,s[i]-'0');
		if(t[i]!=t[i+1])
			T[++cntt]=Val(i,t[i]-'0');
	}
	int ans=1e9;
	for(int i=1;i<=cntt;i++)
	{
		if(S[1].kind!=T[i].kind)continue;
		int sum=0;
		for(int j=1;j<i;j++)
			sum+=T[j].pos;
		int now1=1,now2=i;
		while(now1<=cnts&&now2<=cntt)
		{
			sum+=abs(S[now1].pos-T[now2].pos);
			now1++;
			now2++;
		}
		while(now1<=cnts)
		{
			sum+=n-S[now1].pos;
			now1++;
		}
		while(now2<=cntt)
		{
			sum+=n-T[now2].pos;
			now2++;
		}
		ans=min(ans,sum);
	}
	for(int i=1;i<=cnts;i++)
	{
		if(T[1].kind!=S[i].kind)continue;
		int sum=0;
		for(int j=1;j<i;j++)
			sum+=S[j].pos;
		int now1=i,now2=1;
		while(now1<=cnts&&now2<=cntt)
		{
			sum+=abs(S[now1].pos-T[now2].pos);
			now1++;
			now2++;
		}
		while(now1<=cnts)
		{
			sum+=n-S[now1].pos;
			now1++;
		}
		while(now2<=cntt)
		{
			sum+=n-T[now2].pos;
			now2++;
		}
		ans=min(ans,sum);
	}
	printf("%d\n",ans);
	return 0;
}