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 <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

string S, T; vector<int>V1, V2; int N;

int solve() {
	int minx = (1 << 30);
	for (int i = 0; i <= N; i++) {
		if (i != S.size()) {
			if (S[i] != T[0] || (i >= 1 && S[i] == S[i - 1])) continue;
		}
		if (i == S.size()) {
			if (S[i - 1] == T[0]) continue;
		}
		int score = 0;
		for (int j = 0; j < i; j++) {
			if (S[j] != S[j + 1]) score += (j + 1);
		}
		int pos1 = lower_bound(V1.begin(), V1.end(), i) - V1.begin();
		int pos2 = lower_bound(V2.begin(), V2.end(), 0) - V2.begin();

		while (true) {
			pos1++; pos2++;
			if (pos1 == V1.size() || pos2 == V2.size()) break;
			score += abs(V1[pos1] - V2[pos2]);
		}
		for (int i = pos1; i < V1.size(); i++) score += abs((int)S.size() - V1[i]);
		for (int i = pos2; i < V2.size(); i++) score += abs((int)T.size() - V2[i]);
		minx = min(minx, score);
	}
	int S1 = 0;
	for (int i = 0; i < V1.size(); i++) S1 += abs(V1[i] - 0);
	for (int i = 0; i < V2.size(); i++) S1 += abs(N - V2[i]);
	minx = min(minx, S1);
	int S2 = 0;
	for (int i = 0; i < V1.size(); i++) S2 += abs(N - V1[i]);
	for (int i = 0; i < V2.size(); i++) S2 += abs(V2[i] - 0);
	minx = min(minx, S2);
	return minx;
}

int main() {
	cin >> N >> S >> T;
	V1.push_back(0); for (int i = 0; i < S.size() - 1; i++) { if (S[i] != S[i + 1]) V1.push_back(i + 1); } V1.push_back(S.size());
	V2.push_back(0); for (int i = 0; i < T.size() - 1; i++) { if (T[i] != T[i + 1]) V2.push_back(i + 1); } V2.push_back(T.size());
	
	int v1 = solve(); swap(S, T); swap(V1, V2);
	int v2 = solve(); swap(S, T); swap(V1, V2);
	cout << min(v1, v2) << endl;
	return 0;
}