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 = 5000;
int n, ans = 1e9;
char s[maxn + 10], t[maxn + 10];
vector<int> a, b;

void solve(char *s, vector<int> &a) {
	for (int i = 1; i < n; ++i)
		if (s[i] != s[i + 1]) a.push_back(i);
}

int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 0; i < 5000; ++i)
		a.push_back(0);
	if (s[1] == '1') a.push_back(0);
	solve(s, a);
	for (int i = 0; i < 5000; ++i)
		a.push_back(n);
	scanf("%s", t + 1);
	if (t[1] == '1') b.push_back(0);
	solve(t, b);
	for (int i = 0; i < (int)a.size(); i += 2) {
		int l = i, r = i + (int)b.size() - 1, now = 0;
		if (r >= (int)a.size()) break;
		for (int j = 0; j < l; ++j) now += a[j];
		for (int j = l; j <= r; ++j)
			now += abs(a[j] - b[j - l]);
		for (int j = r + 1; j < (int)a.size(); ++j)
			now += n - a[j];
		ans = min(ans, now);
	}
	printf("%d", ans);
}
