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;

typedef pair<int,int> pi;

const int maxn = 5010;

int n;
char s[maxn], t[maxn];

vector<pi> vec1, vec2;

int main() {
	scanf("%d", &n);
	scanf("%s%s", s+1, t+1);
	for (int i = 1; i <= n; i++) vec1.push_back(pi(i & 1, 0));
	if (vec1[n-1].first != (s[1] - '0')) vec1.push_back(pi(s[1] - '0', 0));
	for (int i = 1; i <= n; i++) {
		if (s[i] != s[i+1]) {
			vec1.push_back(pi((s[i] - '0')^1, i));
		}
	}
	for (int i = 1; i <= n; i++) vec1.push_back(pi(vec1[vec1.size()-1].first^1, n));
	vec2.push_back(pi(t[1] - '0', 0));
	for (int i = 1; i <= n; i++) {
		if (t[i] != t[i+1]) {
			vec2.push_back(pi((t[i] - '0')^1, i));
		}
	}
	int ans = 0x3f3f3f3f;
	int sz = int (vec2.size());
	for (int i = 0; i+sz-1 < vec1.size(); i++) {
		if (vec1[i].first != vec2[0].first) continue;
		int res = 0;
		for (int j = 0; j < sz; j++) res += abs(vec1[i+j].second - vec2[j].second);
		for (int j = 0; j < i; j++) res += abs(vec1[j].second - 0);
		for (int j = i+sz; j < vec1.size(); j++) res += abs(vec1[j].second - n);
		if (res < ans) ans = res;
	}
	printf("%d\n", ans);
	return 0;
}