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 pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 200005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
const int MOD = 1000000007;
int inc(int a,int b) {
	return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
	return 1LL * a * b % MOD;
}
int fpow(int x,int c) {
	int res = 1,t = x;
	while(c) {
		if(c & 1) res = mul(res,t);
		t = mul(t,t);
		c >>= 1;
	}
	return res;
}
int N,st[2],ed[2];
char s[5005],t[5005];
vector<int> a,b;
void Init() {
	read(N);
	scanf("%s%s",s + 1,t + 1);
	for(int i = 1 ; i <= 10010 ; ++i) {
		a.pb(0);b.pb(0);
	}
	if(s[1] == '0') a.pb(0);
	if(t[1] == '0') b.pb(0);
	st[0] = a.size() - 1;st[1] = b.size() - 1;
	for(int i = 1 ; i < N ; ++i) {
		if(s[i] != s[i + 1]) a.pb(i);
		if(t[i] != t[i + 1]) b.pb(i);
	}
	ed[1] = b.size();
	for(int i = 1 ; i <= 10010 ; ++i) {
		a.pb(N);b.pb(N);
	}
}
void Solve() {
	int p = st[0] - 2,q = ed[1] + 2;
	if((p & 1) != (q & 1)) ++q;
	int ans = N * N;
	while(q >= st[1] - N - 2) {
		int t0 = p + 1,t1 = q + 1;
		int res = abs(a[p] - b[q]);
		while(a[t0] != N || b[t1] != N) {
			res += abs(a[t0] - b[t1]);
			++t0;++t1;
		}
		t0 = p - 1,t1 = q - 1;
		while(a[t0] != 0 || b[t1] != 0) {
			res += abs(a[t0] - b[t1]);
			--t0;--t1;
		}
		ans = min(ans,res);
		q -= 2;
	}
	out(ans);enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Init();
	Solve();
}
