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>
using namespace std;

const int maxn = 1e4, inf = 1e9;
int n, k, l, a[maxn + 3], b[maxn + 3];
char s[maxn + 3], t[maxn + 3];

int _abs(int x) {
	return x < 0 ? -x : x;
}

int solve(int p, int q) {
	int ret = 0;
	for (int i = 0; i + p <= k || i + q <= l; i++) {
		int x = i + p <= k ? a[i + p] : n;
		int y = i + q <= l ? b[i + q] : n;
		ret += _abs(x - y);
	}
	for (int i = 1; p - i >= 1 || q - i >= 1; i++) {
		int x = p - i >= 1 ? a[p - i] : 0;
		int y = q - i >= 1 ? b[q - i] : 0;
		ret += _abs(x - y);
	}
	return ret;
}

int main() {
	scanf("%d %s %s", &n, s + 1, t + 1);
	for (int i = 1; i < n; i++) {
		if (s[i] != s[i + 1]) {
			a[++k] = i;
		}
	}
	for (int i = 0; i < 3; i++) {
		a[++k] = 0, a[++k] = n;
	}
	for (int i = 1; i < n; i++) {
		if (t[i] != t[i + 1]) {
			b[++l] = i;
		}
	}
	for (int i = 0; i < 3; i++) {
		b[++l] = 0, b[++l] = n;
	}
	if (t[1] != s[1]) {
		b[++l] = 0;
	}
	sort(a + 1, a + k + 1);
	sort(b + 1, b + l + 1);
	int ans = inf;
	for (int i = 1; i <= k; i += 2) {
		ans = min(ans, solve(i, 1));
	}
	for (int i = 1; i <= l; i += 2) {
		ans = min(ans, solve(1, i));
	}
	printf("%d\n", ans);
	return 0;
}