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 inf 2123333333

int h1[20010],h2[20010],n,tt1,tt2;
char s1[5010],s2[5010];

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline int abs1(int x) { return (x>0)?x:-x; }

inline void pre_gao()
{
	tt1=tt2=0;
	if (s1[1]!=s2[1]) h1[++tt1]=0;
	for (int i=1;i<=5009;i++) h1[++tt1]=0;
	for (int i=1;i<=n;i++) if (s1[i]!=s1[i+1]) h1[++tt1]=i;
	for (int i=1;i<=5010;i++) h1[++tt1]=n;
	h2[++tt2]=0;
	for (int i=1;i<=n;i++) if (s2[i]!=s2[i+1]) h2[++tt2]=i;
}

int main()
{
	n=rd();
	scanf("%s%s",s1+1,s2+1);
	pre_gao();
	int ans=inf;
	for (int i=1;i+tt2-1<=tt1;i+=2)
	{
		int res=0;
		for (int j=1;j<=tt2;j++) res+=abs1(h1[i+j-1]-h2[j]);
		for (int j=1;j<i;j++) res+=abs1(h1[j]);
		for (int j=i+tt2;j<=tt1;j++) res+=abs1(h1[j]-n);
		ans=min(ans,res);
	}
	printf("%d\n",ans);
	return 0;
}