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<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2e4 + 5;
char s[maxn], t[maxn];
int n, ps[maxn], pt[maxn], cs, ct, ans = 1 << 30, nans;
int tmps[maxn], tmpt[maxn];

int GetAns(int x) {
	int r = max(x + cs, ct), ts = 0;
	int l = min(x, 0), tt = 0, nans = 0;
	for(register int i = l; i < r; ++i) {
		if(i >= x && i < x + cs) tmps[++ts] = ps[i - x];
		if(i < x) tmps[++ts] = -1;
		if(i >= x + cs) tmps[++ts] = n - 1;
		if(i >= 0 && i < ct) tmpt[++tt] = pt[i];
		if(i < 0) tmpt[++tt] = -1;
		if(i >= ct) tmpt[++tt] = n - 1;
	}
	for(register int i = 1; i <= ts; ++i) {
		nans += abs(tmps[i] - tmpt[i]);
	}
	return nans;
}

int main() {
	scanf("%d", &n);
	scanf("%s%s", s, t);
	if(s[0] == '0') ps[cs++] = -1;
	if(t[0] == '0') pt[ct++] = -1;
	for(register int i = 0; i < n - 1; ++i) {
		if(s[i] != s[i + 1]) ps[cs++] = i;
		if(t[i] != t[i + 1]) pt[ct++] = i;
	}
	for(register int i = -cs; i <= ct; ++i) {
		if(abs(i) & 1) continue;
		ans = min(ans, GetAns(i));
	}
	printf("%d", ans);
	return 0;
}