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;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
inline void myassert(bool a,string s){ if(!a)cerr<<s<<endl,exit(0);}
inline int read()
{
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return ~f?s:-s;
}

const int maxn=5e3+20;
const int inf=0x3f3f3f3f;

#define pii pair<int,int>

int n;
vector<pii >s;
vector<pii >t;
char str[maxn];

inline void init()
{
	n=read();
	scanf("%s",str+1);
	s.push_back(mkr(0,str[1]=='0'));
	REP(i,1,n-1)if(str[i]!=str[i+1])s.push_back(mkr(i,str[i]=='1'));
	s.push_back(mkr(n,str[n]=='1'));
	scanf("%s",str+1);
	t.push_back(mkr(0,str[1]=='0'));
	REP(i,1,n-1)if(str[i]!=str[i+1])t.push_back(mkr(i,str[i]=='1'));
	t.push_back(mkr(n,str[n]=='1'));
	if(SZ(s)>SZ(t))swap(s,t);
}

inline void doing()
{
	vector<pii >Top; Top.push_back(s.front());
	REP(i,1,n)Top.push_back(mkr(0,Top.back().se^1));
	reverse(Top.begin(),Top.end()); Top.pop_back();
	Top.insert(Top.end(),s.begin(),s.end());
	REP(i,1,n)Top.push_back(mkr(n,Top.back().se^1));

	int ans=inf;
	
	REP(i,0,SZ(Top)-SZ(t))if(Top[i].se==t[0].se)
	{
		int sum=0;
		REP(j,0,i-1)sum+=Top[j].fi;
		REP(j,i+SZ(t),SZ(Top)-1)sum+=n-Top[j].fi;
		REP(j,0,SZ(t)-1)
			sum+=abs(Top[i+j].fi-t[j].fi);
		chkmin(ans,sum);
	}
	printf("%d\n",ans);
}

int main()
{
	init();
	doing();
	return 0;
}
