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 fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 15005;
int n;char s[N],t[N];
int a[N],A,b[N],B,res=2e9;
void init(char *s, int *a, int &l){
	rep(i,1,n)a[++l]=0;
	rep(i,1,n-1)if(s[i]!=s[i+1])a[++l]=i;
	rep(i,1,n)a[++l]=n;
}
int Abs(int x){return x>0?x:-x;}
int main() {
	read(n);scanf("%s%s",s+1,t+1);
	init(s,a,A);init(t,b,B);
	for(int i=n+1-(s[1]!=t[1]);i>=1;i-=2){int pa=i,pb=n+1;
		int now=0;bool gg=0;
		while(pa<=A&&pb<=B&&a[pa]+b[pb]<n*2){now+=Abs(a[pa]-b[pb]);pa++;pb++;}
		gg|=(pa<=A&&a[pa]<n)|(pb<=B&&b[pb]<n);if(!gg)res=min(res,now);
	}
	for(int i=n+1-(s[1]!=t[1]);i>=1;i-=2){int pa=n+1,pb=i;
		int now=0;bool gg=0;
		while(pa<=A&&pb<=B&&a[pa]+b[pb]<n*2){now+=Abs(a[pa]-b[pb]);pa++;pb++;}
		gg|=(pa<=A&&a[pa]<n)|(pb<=B&&b[pb]<n);if(!gg)res=min(res,now);
	}
	cout<<res;return 0;
}
