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 <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

const int MAXN = 5e3 + 10, INF = 1e9;

int n, n1, n2;
int a[MAXN << 2], b[MAXN << 2];
char s[MAXN], t[MAXN];

int main() {
	scanf("%d %s %s", &n, s + 1, t + 1);
	for (int i = 1; i < n; ++i) if (s[i] != s[i + 1]) a[(++n1) + n + 20] = i;
	for (int i = 1; i < n; ++i) if (t[i] != t[i + 1]) b[(++n2) + n + 20] = i;
	for (int i = 1; i <= n + 20; ++i) a[n1 + n + 20 + i] = b[n2 + n + 20 + i] = n;
	int ans = INF;
	for (int i = -n1 - 2; i <= n2 + 2; ++i) if ((i & 1) != (s[1] == t[1])) {
		int now = 0;
		for (int j = std::min(0, -i) + n; j <= std::max(n1, -i + n2 + 1) + n + 30; ++j) now += abs(a[j] - b[i + j]);
		ans = std::min(ans, now);
	}
	printf("%d\n", ans);
	return 0;
}