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 ll long long
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
int n;
char s[10100],t[10100];
vector<pair<int,int> > S,T;
int main(){
	read(n);
	cin>>s+1;
	cin>>t+1;
	if(n==1){
		cout<<(s[1]!=t[1])<<'\n';
		return 0;
	}
	if(n==2){
		cout<<(s[1]!=t[1])+(s[2]!=t[2])<<'\n';
		return 0;
	}
	for(int i=1;i<n;i++)
		if(s[i]!=s[i+1]) S.emplace_back(i,s[i]);
	for(int i=1;i<n;i++)
		if(t[i]!=t[i+1]) T.emplace_back(i,t[i]);
	int ans=1e9;
	for(int i=0;i<T.size();i++)
		if(S[0].second==T[i].second){
			int now=0;
			for(int j=0;j<i;j++) now+=T[j].first;
			for(int j=i;j<T.size();j++)
				now+=abs(T[j].first-(j-i<S.size()?S[j-i].first:n));
			for(int j=T.size()-i;j<S.size();j++)
				now+=n-S[j].first;
			ans=min(ans,now);
		}
	swap(S,T);
	for(int i=0;i<T.size();i++)
		if(S[0].second==T[i].second){
			int now=0;
			for(int j=0;j<i;j++) now+=T[j].first;
			for(int j=i;j<T.size();j++)
				now+=abs(T[j].first-(j-i<S.size()?S[j-i].first:n));
			for(int j=T.size()-i;j<S.size();j++)
				now+=n-S[j].first;
			ans=min(ans,now);
		}
	cout<<ans<<'\n';
	return 0;
}
