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>
using namespace std;
typedef long long LL;

int main(){
	cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
	LL n;
	cin >> n;
	string s;
	string t;
	cin >> s >> t;
	vector<LL> b1, b2;
	for(LL i = 0; i + 1 < n; i++){
		if(s[i] == s[i+1]) b1.push_back(i+1);
		if(t[i] == t[i+1]) b2.push_back(i+1);
	}
	sort(b1.begin(), b1.end());
	sort(b2.begin(), b2.end());
	LL best = 1e15;

	int par = s[0] != t[0];
	for(LL dx = -6000; dx <= 6000; dx++){
		int par2 = dx & 1;
		if(par2 != par) continue;
		LL minv = min(0LL, -dx) - 10;
		LL maxv = max(n, n-dx) + 10;
		LL val = 0;
		for(LL v = minv; v <= maxv; v++){
			LL w = v + dx;
			LL g1, g2;
			if(v < 0){
				g1 = 0;
			} else if(v >= b1.size()){
				g1 = n;
			} else {
				g1 = b1[v];
			}
			if(w < 0){
				g2 = 0;
			} else if(w >= b2.size()){
				g2 = n;
			} else {
				g2 = b2[w];
			}
			val += abs(g2 - g1);
		}
		best = min(best, val);
	}
	cout << best << endl;
}