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>
using namespace std;

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;

	char buf[bufl],*s=buf,*t=buf;

	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}

	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}

	template<typename T> inline int ts(T *s)
	{
		int a=0,c=fetch();
		while(c<=32 && c!=EOF)c=fetch();
		while(c>32 && c!=EOF)s[a++]=c,c=fetch();
		return a;
	}
}
using ae86::ty;
using ae86::ts;

const int _ = 5007;

int n,sa[_],sb[_],na,nb;
vector<int> va,vb;

int main()
{
	n=ty(),ts(sa+1),ts(sb+1);

	for(int i=1;i<=n;i++)sa[i]-=48,sb[i]-=48;
	for(int i=1;i<n;i++)
	{
		if(sa[i]!=sa[i+1])va.emplace_back(i);
		if(sb[i]!=sb[i+1])vb.emplace_back(i);
	}
	na=va.size(),nb=vb.size();

	if(!na || !nb)
	{
		int cnt=0;
		for(int i=1;i<=n;i++)cnt+=sa[i]!=sb[i];
		printf("%d\n",cnt);
		
		return 0;
	}

	int ans=1e9,dlt=sa[va[0]]!=sb[vb[0]];
	for(int i=-(na+((na&1)^dlt));i<=nb+((nb&1)^dlt);i+=2)
	{
		int sum=0;
		for(int j=min(0,-i),k=j+i;j<max(na,nb-i);j++,k++)
		{
			int xa=0,xb=0;
			if(j>=0 && j<na)xa=va[j];
			else if(j>=na)xa=n;
			if(k>=0 && k<nb)xb=vb[k];
			else if(k>=nb)xb=n;
			sum+=abs(xa-xb);
		}
		ans=min(ans,sum);
	}

	printf("%d\n",ans);
	
	return 0;
}
