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>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int L;
	string S[2];
	cin >> L >> S[0] >> S[1];
	int N[2];
	vector<int> pos0[2];
	for(int k = 0; k < 2; k++) {
		for(int i = 1; i < L; i++)
			if(S[k][i] == S[k][i-1]) pos0[k].push_back(i-1);
		N[k] = pos0[k].size();
	}
	if(N[0]+N[1] == 0) {
		if(S[0][0] == S[1][0]) cout << "0\n";
		else cout << L << "\n";
		return 0;
	}
	vector<int> id_gt[2];
	for(int k = 0; k < 2; k++) {
		id_gt[k].resize(N[k]);
		int a = 0;
		for(int i = 0; i < N[k]; i++) {
			while(a < N[1-k] && pos0[1-k][a] < pos0[k][i]) a++;
			if(k == 1) while(a < N[1-k] && pos0[1-k][a] <= pos0[k][i]) a++;
			id_gt[k][i] = a;
		}
	}
	vector<cat> cost(N[0]+N[1]+1, 0), add(N[0]+N[1]+1, 0);
	for(int i = 0; i < N[0]; i++) {
		// cost[d] += A[i]: A[i] > B[i+d]
		add[N[0]-i] += pos0[0][i];
		add[N[0]+id_gt[0][i]-i] -= pos0[0][i];
		// cost[d] -= A[i]: A[i] <= B[i+d]
		add[N[0]+id_gt[0][i]-i] -= pos0[0][i];
		add[N[0]+N[1]-i] += pos0[0][i];
	}
	for(int i = 0; i < N[1]; i++) {
		// cost[d] += B[i]: A[i-d] <= B[i]
		add[N[0]+i-id_gt[1][i]+1] += pos0[1][i];
		add[N[0]+i+1] -= pos0[1][i];
		// cost[d] -= B[i]: A[i-d] > B[i]
		add[N[0]+i-N[0]+1] -= pos0[1][i];
		add[N[0]+i-id_gt[1][i]+1] += pos0[1][i];
	}
	for(int i = 0; i < N[0]; i++) {
		add[N[0]+N[1]-i] += L-1-pos0[0][i];
		// add[N[0]+N[1]+1] -= L-1-pos0[0][i];
		add[0] += 1+pos0[0][i];
		add[N[0]-i] -= 1+pos0[0][i];
	}
	for(int i = 0; i < N[1]; i++) {
		add[N[0]+i+1] += 1+pos0[1][i];
		// add[N[0]+N[1]+1] -= 1+pos0[1][i];
		add[0] += L-1-pos0[1][i];
		add[i+1] -= L-1-pos0[1][i];
	}
	cat a = 0;
	for(int i = 0; i <= N[0]+N[1]; i++) {
		a += add[i];
		cost[i] += a;
	}
	int dif = (S[0][0] != S[1][0]) ^ (N[0]&1);
	cat ans = cost[dif];
	for(int i = dif; i <= N[0]+N[1]; i += 2) ans = min(ans, cost[i]);
	cout << ans << "\n";
	return 0;
}

// look at my code
// my code is amazing
