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 EB emplace_back

typedef std::vector <int> vector;
const int N = 5054;

int n;
char s[N], t[N];
vector S, T;

inline void down(int &x, const int y) {x > y ? x = y : 0;}
inline int get(const vector &vec, int idx) {return (size_t)idx < vec.size() ? vec[idx] : (idx >> 31 ? 0 : n);}

void analysis(const char *_str, vector &ret) {
	for (int i = 0; i < n; ++i) if (i ? _str[i - 1] != _str[i] : *_str == 49) ret.EB(i);
}

int compute(int offset) {
	int i, j, nS = S.size(), nT = T.size(), ret = 0;
	for (offset >> 31 ? (i = 0, j = offset) : (i = -offset, j = 0); i < nS || j < nT; ++i, ++j) ret += abs(get(S, i) - get(T, j));
	return ret;
}

int main() {
	int d, inf, sup, ans = INT_MAX;
	scanf("%d%s%s", &n, s, t);
	analysis(s, S), analysis(t, T);
	inf = ~S.size() & -2, sup = (T.size() | 1) + 1;
	for (d = inf; d <= sup; d += 2) down(ans, compute(d));
	printf("%d\n", ans);
	return 0;
}