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 = 5e3 + 5;
const int INF  = 1e9;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n;
vector <int> a, b;
char s[MAXN], t[MAXN];
bool fail(vector <int> &a, int cnt, int &ans) {
	vector <int> tmp = a;
	if (cnt == 0) return false;
	if (cnt >= 0) {
		int now = 0;
		while (cnt > 0) {
			if (a.empty()) return true;
			if (a.back() == 1) now++;
			else {
				cnt--;
				ans += now + 1;
				now += 2;
			}
			a.pop_back();
		}
		while (now--) a.push_back(1);
	} else {
		cnt = -cnt;
		int now = 0, state = 0;
		while (cnt > 0) {
			if (a.empty()) return true;
			if (a.back() == 2) now++;
			else if (state == 0) state = 1, ans += now;
			else {
				ans += now + 1;
				cnt--, now++;
				state = 0;
			}
			a.pop_back();
		}
		while (now--) a.push_back(2);
	}
	return false;
}
void debug(vector <int> &a) {
	for (auto x : a)
		cerr << x << ' ';
	cerr << endl;
}
int func(int x) {
	int y = b.size() - x - a.size();
	vector <int> c = a; int ans = 0;
	reverse(c.begin(), c.end());
	if (fail(c, x, ans)) return INF;
	reverse(c.begin(), c.end());
	if (fail(c, y, ans)) return INF;
	vector <int> e, d;
	for (unsigned i = 0; i < b.size(); i++) {
		if (b[i] == 2) d.push_back(i);
		if (c[i] == 2) e.push_back(i);
	}
	assert(d.size() == e.size());
	for (unsigned i = 0; i < d.size(); i++)
		ans += abs(d[i] - e[i]);
	return ans;
}
int main() {
	read(n);
	scanf("\n%s", s + 1);
	scanf("\n%s", t + 1);
	if (n == 1) {
		if (s[1] != t[1]) cout << 1 << endl;
		else cout << 0 << endl;
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		if (s[i] == s[i - 1]) {
			a.pop_back();
			a.push_back(2);
		} else a.push_back(1);
		if (t[i] == t[i - 1]) {
			b.pop_back();
			b.push_back(2);
		} else b.push_back(1);
	}
	int ans = INF;
	for (int i = -n; i <= n; i++)
		if ((s[1] == t[1]) ^ (i % 2 != 0)) chkmin(ans, func(i));
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	for (int i = -n; i <= n; i++)
		if ((s[n] == t[n]) ^ (i % 2 != 0)) chkmin(ans, func(i));
	cout << ans << endl;
	return 0;
}