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 x first
#define y second
#define pb push_back
#define mp make_pair
#define inf (0x3f3f3f3f)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Rep(i, a) for (int i = 0; i < a; ++ i)
#define For(i, a, b) for (int i = a; i <= b; ++ i)
#define Forr(i, a, b) for (int i = a; i >= b; -- i)
#define Travel(i, x) for (int i = head[x]; i; i = nxt[i])

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

template<class T>inline T read(T &_) {
	T __ = getchar(), ___ = 1; _ = 0;
	for (; !isdigit(__); __ = getchar()) if (__ == '-') ___ = -1;
	for (; isdigit(__); __ = getchar()) _ = (_ << 3) + (_ << 1) + (__ ^ 48);
	return _ *= ___;
}

template<class T>inline bool chkmax(T &_, T __) { return _ < __ ? _ = __, 1 : 0; }
template<class T>inline bool chkmin(T &_, T __) { return _ > __ ? _ = __, 1 : 0; }

inline void proStatus() {
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>());
}

const int N = 5e3 + 7;

PII a[N], b[N];

char s[N], t[N];

int n, ans = inf, c, d;

void Solve() { 
	For(i, 0, n) { 
		if ((a[1].y + b[1].y + i) & 1) continue;
		int res = 0, now = 1;
		while (now <= c) { 
			int ps = a[now].x, pt = now + i <= d ? b[now + i].x : n + 1;
			res += abs(pt - ps), ++ now;
		}
		while (now + i <= d) res += n + 1 - b[now + i].x, ++ now;
		For(j, 1, i) {
			int pt = j <= d ? b[j].x : n + 1; 
			res += pt - 1; 
		}
		chkmin(ans, res);
	}
}

int main() {

	scanf("%d%s%s", &n, s + 1, t + 1);

	For(i, 1, n) { 
		if (s[i] != s[i - 1]) 
			a[++ c] = mp(i, s[i] ^ 48);
		if (t[i] != t[i - 1]) 
			b[++ d] = mp(i, t[i] ^ 48);
	}
	Solve(), swap(c, d), swap(a, b), Solve();

	printf("%d\n", ans);

	return 0;
}