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;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;

int n;

vi seps(string &s){
	vi ans;
	rep(i,1,n) if(s[i] != s[i-1]) ans.push_back(i);
	return ans;
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	string s, t;
	cin >> s >> t;

	vi ss = seps(s), tt = seps(t);

	int ans = 1e9;

	rep(dif, -sz(ss)-1, sz(tt)+2) if((dif + (s[0]==t[0]))%2){
		int cur = 0;
		rep(i, min(-dif,0), max(sz(ss), sz(tt)-dif)){
			int j = i + dif;
			int sx = i<0 ? 0 : i<sz(ss) ? ss[i] : n;
			int tx = j<0 ? 0 : j<sz(tt) ? tt[j] : n;
			cur += abs(sx - tx);
		}
		ans = min(ans, cur);
	}
	cout << ans << endl;
}
