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 <stdio.h>
#include <algorithm>
#include <deque>
using namespace std;

int N; char S[5050], T[5050];

int main()
{
	scanf ("%d %s %s",&N,S,T);
	deque<int> s, t;

	for (int i=1;i<N;i++) if (S[i-1] == S[i]) s.push_back(i);
	for (int i=1;i<N;i++) if (T[i-1] == T[i]) t.push_back(i);

	long long ans = 1e18;
	for (int mk=-N;mk<=N;mk++) if ((S[0] - '0' + mk % 2 + 2 + T[0] - '0') % 2 == 0){
		auto p = s, q = t;
		if (mk < 0) for (int k=0;k<-mk;k++) p.push_front(-1);
		if (mk > 0) for (int k=0;k<mk;k++) q.push_front(-1);
		while (p.size() < q.size()) p.push_back(-2);
		while (q.size() < p.size()) q.push_back(-2);

		long long sum = 0;
		for (int i=0;i<p.size();i++){
			if (p[i] == -1 && q[i] == -1);
			else if (p[i] == -2 && q[i] == -2);
			else if (p[i] == -1 && q[i] == -2) sum += N;
			else if (p[i] == -2 && q[i] == -1) sum += N;
			else if (p[i] == -1) sum += q[i];
			else if (q[i] == -1) sum += p[i];
			else if (p[i] == -2) sum += N - q[i];
			else if (q[i] == -2) sum += N - p[i];
			else sum += abs(p[i] - q[i]);
		}

		if (ans > sum)
			ans = sum;
	}

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

	return 0;
}