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;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

int main(){
	int N; cin >> N;	
	string s,t; cin >> s; cin >> t;
	vector<int> vs(N+1),vt(N+1);
	vs[0] = s[0]-'0';
	vt[0] = t[0]-'0';
	repp(i,1,N){
		vs[i] = (s[i-1] != s[i]);
		vt[i] = (t[i-1] != t[i]);
	}
	vs[N] = s[N-1]-'0';
	vt[N] = t[N-1]-'0';
	vector<int> x,y;
	int c = 0;
	repp(i,0,N+1){
		if(vs[i] == 0){
			--c;
			x.push_back(i);
		}
		if(vt[i] == 0){
			++c;
			y.push_back(i);
		}
	}
	if(c < 0){
		swap(vs,vt);
		swap(x,y);
		c = -c;
	}
	int ans = 1e9+7;
	repp(i,-(x.size()/2),c/2+(x.size()/2)+1){
		vector<int> p = x, q = y;
		repp(j,i,0){
			q.push_back(0);
			q.push_back(1);
		}
		repp(j,0,i){
			p.push_back(0);
			p.push_back(1);
		}
		repp(j,i,c/2){
			p.push_back(N-1);
			p.push_back(N);
		}
		repp(j,c/2,i){
			q.push_back(N-1);
			q.push_back(N);
		}
		sort(p.begin(),p.end());
		sort(q.begin(),q.end());
		int d = 0;
		repp(i,0,p.size()) d += abs(p[i]-q[i]);
		ans = min(ans,d+c/2+max(0,max(-i,i-c/2))*2);
	}
	cout << ans << endl;
	return 0;
}
