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>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define abs(x) ((x)>0?(x):-(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
//#define file
using namespace std;

bool a[5001],b[5001];
int d1[5001],d2[5001],D[10001],n,N,i,j,k,l,s1,s2,ans,sum,tot;
char ch;

int main()
{
	#ifdef file
	freopen("AGC030E.in","r",stdin);
	#endif
	
	scanf("%d",&n);N=n/2;
	fo(i,1,n) {ch=getchar();while (ch!='0' && ch!='1') ch=getchar(); a[i]=ch=='1';}
	fo(i,1,n) {ch=getchar();while (ch!='0' && ch!='1') ch=getchar(); b[i]=ch=='1';}
	fo(i,1,n-1)
	{
		if (a[i]==a[i+1]) d1[++s1]=i;
		if (b[i]==b[i+1]) d2[++s2]=i;
	}
	if (!s1 && !s2) {if (a[1]==b[1]) printf("0\n"); else printf("%d\n",n);return 0;}
	
	ans=2133333333;
	fo(i,-N,N)
	if ((a[1]^(i&1))==b[1] && abs(s2-(s1+i))<=N)
	{
		j=s2-(s1+i);
		
		tot=sum=0;
		fo(k,1,-i) sum+=d1[k];
		fo(k,1,i) D[++tot]=0;
		fo(k,1+max(-i,0),s1-max(-j,0)) D[++tot]=d1[k];
		fo(k,1,-j) sum+=n-d1[s1-k+1];
		fo(k,1,j) D[++tot]=n;
		
		if (tot>s2) continue;
		
		fo(k,1,tot) sum+=abs(D[k]-d2[k]);
		ans=min(ans,sum);
	}
	
	printf("%d\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}