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 LL long long
#define pii pair<int,int>
using namespace std;
const int inf = 2147483647;
const int N = 5001;

int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}
void put(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

int n, a[N * 3], b[N];
char s1[N], s2[N];

int solve() {
	int l1 = 0, l2 = 0;
	for(int i = 1; i <= n; i++) a[++l1] = 0;
	for(int i = 1; i < n; i++) if(s1[i] == '0' && s1[i + 1] == '1') a[++l1] = i;
	for(int i = 1; i < n; i++) if(s2[i] == '0' && s2[i + 1] == '1') b[++l2] = i;
	for(int i = 1; i <= n; i++) a[++l1] = n;
	int hh = 999999999;
	for(int i = 1; i <= l1 - l2 + 1; i++) {
		int ans = 0;
		for(int j = 1; j < i; j++) ans += a[j];
		for(int j = 0; j < l2; j++) ans += abs(b[j + 1] - a[j + i]);
		for(int j = l2; j < l1 - i; j++) ans += n - a[j + i];
		hh = _min(hh, ans);
	} return hh;
}

int main() {
	n = read();
	scanf("%s%s", s1 + 1, s2 + 1);
	if(n == 1 && s1[1] != s2[1]) puts("1");
	else if(n == 2 && s1[1] != s2[1] && s1[2] != s2[2]) puts("2");
	else {
		int ans = solve();
		for(int i = 1; i <= n; i++) s1[i] ^= 1, s2[i] ^= 1;
		ans += solve();
		put(ans), puts("");
	} return 0;
}
