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<stdio.h>
char s[8192],t[8192];
int wzs[16384],wzt[16384];
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s%s",s,t);
	int nums=s[0]-'0';
	int numt=t[0]-'0';
	for(int i=1;i<n;i++)
	{
		if(s[i]!=s[i-1])
		{
			wzs[nums]=i;
			nums++;
		}
		if(t[i]!=t[i-1])
		{
			wzt[numt]=i;
			numt++;
		}
	}
	while(nums<6000)
	{
		wzs[nums]=n;
		nums++;
	}
	while(numt<6000)
	{
		wzt[numt]=n;
		numt++; 
	}
	int ans=1000000000;
	for(int i=-6000;i<=6000;i+=2)
	{
		int ans2=0;
		for(int j=-6000;j<=12000;j++)
		{
			int val0=j;
			int val1=i+j;
			if(val0<0)
			{
				val0=0;
			}
			else if(val0>=6000)
			{
				val0=n;
			}
			else
			{
				val0=wzs[val0];
			}
			if(val1<0)
			{
				val1=0;
			}
			else if(val1>=6000)
			{
				val1=n;
			}
			else
			{
				val1=wzt[val1];
			}
			if(val0<val1)
			{
				ans2+=val1-val0;
			}
			else
			{
				ans2+=val0-val1;
			}
		}
		if(ans2<ans)
		{
			ans=ans2;
		}
	}
	printf("%d\n",ans);
	return 0;
}