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>
#define N 10001
int c[N],d[N],i,j,k,n,s,t,x,y,z;char a[N],b[N];
int main()
{
	scanf("%d%s%s",&n,a+1,b+1),x=1000000000,s=t=2;
	for(i=1;i<n;i++)if(a[i]!=a[i+1])c[++s]=i;
	for(i=1;i<n;i++)if(b[i]!=b[i+1])d[++t]=i;
	for(a[1]!=b[1]?z=c[1],i=2:(z=0,i=1);i<=s;x=x<y?x:y,z+=c[i++],z+=c[i++])
	{
		for(j=i,k=1,y=z;j<=s&&k<=t;j++,k++)y+=c[j]<d[k]?d[k]-c[j]:c[j]-d[k];
		while(j<=s)y+=n-c[j++];
		while(k<=t)y+=n-d[k++];
	}
	for(a[1]!=b[1]?z=d[1],i=2:(z=0,i=1);i<=t;x=x<y?x:y,z+=d[i++],z+=d[i++])
	{
		for(j=1,k=i,y=z;j<=s&&k<=t;j++,k++)y+=c[j]<d[k]?d[k]-c[j]:c[j]-d[k];
		while(j<=s)y+=n-c[j++];
		while(k<=t)y+=n-d[k++];
	}
	return 0*printf("%d\n",x);
}