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 Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 5000
using namespace std;
int n,ans,t1,t2,a1[N+5],a2[N+5];char s1[N+5],s2[N+5];
I void Calc()
{
	RI i,j,Mn=1e9,res;for(i=1;i<=t2;++i)
	{
		for(res=0,j=1;j^i;++j) res+=a2[j];
		for(j=i;j-i+1<=t1&&j<=t2;++j) res+=abs(a1[j-i+1]-a2[j]);
		W(j-i+1<=t1) res+=n-a1[j-i+1],++j;W(j<=t2) res+=n-a2[j],++j;Mn=min(Mn,res);
	}
	for(i=1;i<=t1;++i)
	{
		for(res=0,j=1;j^i;++j) res+=a1[j];
		for(j=i;j<=t1&&j-i+1<=t2;++j) res+=abs(a1[j]-a2[j-i+1]);
		W(j<=t1) res+=n-a1[j],++j;W(j-i+1<=t2) res+=n-a2[j-i+1],++j;Mn=min(Mn,res);
	}ans+=Mn;
}
int main()
{
	RI i;if(scanf("%d%s%s",&n,s1+1,s2+1),n==1) return putchar(48|(s1[1]^s2[1])),0;
	if(n==2&&s1[1]==s1[2]&&s2[1]==s2[2]) return putchar(48+2*(s1[1]^s2[1])),0;
	for(t1=0,i=1;i^n;++i) s1[i]=='0'&&s1[i+1]=='1'&&(a1[++t1]=i);
	for(t2=0,i=1;i^n;++i) s2[i]=='0'&&s2[i+1]=='1'&&(a2[++t2]=i);Calc();
	for(t1=0,i=1;i^n;++i) s1[i]=='1'&&s1[i+1]=='0'&&(a1[++t1]=i);
	for(t2=0,i=1;i^n;++i) s2[i]=='1'&&s2[i+1]=='0'&&(a2[++t2]=i);Calc();
	return printf("%d\n",ans),0;
}