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(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define P pair<int,int>
#define x first
#define y second
#define pb push_back
#define abs(x)(x>0?x:-(x))
using namespace std;
const int N=5005;
int n,ans;
vector<P>S,T;
char s[N],t[N];
void work(vector<P>&a,vector<P>&b){
	int pre=0,s;
	fo(i,0,a.size()-1){
		if(a[i].y==b[0].y){
			s=pre;
			int j=i,k=0;
			for(;j<a.size()&&k<b.size();++j,++k)
				s+=abs(a[j].x-b[k].x);
			for(;j<a.size();++j)s+=n-a[j].x;
			for(;k<b.size();++k)s+=n-b[k].x;
			ans=min(ans,s);
		}
		pre+=a[i].x;
	}
	for(P i:b)pre+=n-i.x;
	ans=min(ans,pre);
}
int main(){
	scanf("%d\n%s\n%s",&n,s+1,t+1);
	if(n<=2){
		fo(i,1,n)if(s[i]!=t[i])++ans;
		cout<<ans;
		return 0;
	}
	fo(i,1,n-1){
		if(s[i]!=s[i+1])S.pb(P(i,s[i]-'0'));
		if(t[i]!=t[i+1])T.pb(P(i,t[i]-'0'));
	}
	ans=1e9;
	work(S,T);
	work(T,S);
	cout<<ans;
}