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 N = 10107;

int a[N], b[N];
int na, nb;
int l[N], r[N];

int main() {
	ios_base::sync_with_stdio(false);
	int n;
	string s, t;
	cin >> n >> s >> t;
	
	for (int i = 1; i < n; ++i) {
		if (s[i] != s[i - 1]) {
			a[na++] = i;
		}
		
		if (t[i] != t[i - 1]) {
			b[nb++] = i;
		}
	}
	
	int ans = 1e9;
	bool eq = s[0] == t[0];
	for (int i = -n - 1; i <= n + 1; ++i) {
		if ((i % 2 == 0) != eq) {
			continue;
		}
		
		int nl = 0, nr = 0;
		
		if (i > 0) {
			fill(l, l + i, 0);
			nl = i;
		} else {
			fill(r, r + (-i), 0);
			nr = -i;
		}
		
		copy(a, a + na, l + nl);
		copy(b, b + nb, r + nr);
		
		nl += na;
		nr += nb;
		
		while (nl < nr) {
			l[nl++] = n;
		}
		
		while (nr < nl) {
			r[nr++] = n;
		}
		int nw = 0;
		for (int j = 0; j < nl; ++j) {
			nw += abs(l[j] - r[j]);
		}
		
		ans = min(ans, nw);
	}
	
	printf("%d\n", ans);
}