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
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAX 5005
using namespace std;
//char nc()
//{
//	static char buf[100000],*p1=buf,*p2=buf;
//	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
char nc(){return getchar();}
int read()
{
	int x=0,y=1;
	char c=nc();
	while(!isdigit(c))
	{
		if(c=='-')y=-1;
		c=nc();
	}
	while(isdigit(c))
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=nc();
	}
	return x*y;
}
int n,ha[MAX],hb[MAX],ta=0,tb=0;
char a[MAX],b[MAX];
int main()
{
	n=read();
	scanf("%s%s",a,b);
	if(a[0]=='1') ha[++ta]=0;
	if(b[0]=='1') hb[++tb]=0;
	for(int i=1;i<n;i++)
	{
		if(a[i]!=a[i-1]) ha[++ta]=i;
		if(b[i]!=b[i-1]) hb[++tb]=i;
	}
	int ANS=INF;
	for(int i=0;i<=tb;i+=2)
	{
		int sm=0,p1=1,p2=1;
		while(p2<=i)
			sm+=hb[p2],p2++;
		while(p1<=ta&&p2<=tb)
			sm+=abs(ha[p1]-hb[p2]),p1++,p2++;
		while(p1<=ta)
			sm+=n-ha[p1],p1++;
		while(p2<=tb)
			sm+=n-hb[p2],p2++;
		ANS=min(ANS,sm);
	}
	for(int i=0;i<=ta;i+=2)
	{
		int sm=0,p1=1,p2=1;
		while(p1<=i)
			sm+=ha[p1],p1++;
		while(p1<=ta&&p2<=tb)
			sm+=abs(ha[p1]-hb[p2]),p1++,p2++;
		while(p1<=ta)
			sm+=n-ha[p1],p1++;
		while(p2<=tb)
			sm+=n-hb[p2],p2++;
		ANS=min(ANS,sm);
	}
	printf("%d",ANS);
	return 0;
}
