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 clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=5005;
int n;
char s[N],t[N];
deque <int> a,b,A,B;
int main(){
	n=read();
	cin>>(s+1)>>(t+1);
	if (s[1]!=t[1])
		a.pb(0);
	For(i,1,n-1){
		if (s[i]!=s[i+1])
			a.pb(i);
		if (t[i]!=t[i+1])
			b.pb(i);
	}
	if (s[n]!=t[n])
		a.pb(n);
	int ans=1e9;
	For(i,-n,n)
		if (i%2==0){
			int t=i;
			A=a,B=b;
			while (t>0)
				A.push_front(0),A.push_front(0),t-=2;
			while (t<0)
				B.push_front(0),B.push_front(0),t+=2;
			while (A.size()<B.size())
				A.pb(n),A.pb(n);
			while (B.size()<A.size())
				B.pb(n),B.pb(n);
			int now=0;
			For(i,0,(int)A.size()-1)
				now+=abs(A[i]-B[i]);
			ans=min(ans,now);
		}
	cout<<ans<<endl;
	return 0;
}