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 INF 2147483647
#define maxn 100010
using namespace std;
char s[maxn];
int pos[2][maxn], cnt[2], n;
int solve(int t1, int t2)
{
	int sum = 0;
	for (int i = 1; i <= t1 - 1; i++)
		sum += pos[0][i];
	for (int i = 1; i <= t2 - 1; i++)
		sum += pos[1][i];
	while (t1 <= cnt[0] || t2 <= cnt[1])
	{
		int p1, p2;
		if (t1 > cnt[0]) p1 = n;
		else p1 = pos[0][t1];
		if (t2 > cnt[1]) p2 = n;
		else p2 = pos[1][t2];
		sum += abs(p1 - p2);
		t1++; t2++;
	}
	return sum;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i <= 1; i++)
	{
		scanf("%s", s + 1);
		int tmp = s[1] - '0' + 4;
		for (int j = 1; j <= tmp; j++)
			pos[i][++cnt[i]] = 0;
		for (int j = 1; j <= n - 1; j++)
			if (s[j] != s[j + 1]) pos[i][++cnt[i]] = j;
	}
	int res = INF;
	for (int i = 1; i <= cnt[1]; i += 2)
		res = min(res, solve(1, i));
	for (int i = 1; i <= cnt[0]; i += 2)
		res = min(res, solve(i, 1));
	printf("%d\n", res);
	return 0;
}