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>
#define meow(args...) fprintf(stderr, args)
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
const int N=1e7+5;
char s[N], t[N];
int mem[2*N], *cnt=mem+N;
int main() {
	int n, x, y=0, k=0;
	long long ans=0;
	assert(scanf("%d%s%s", &n, s, t)==3);
	x=(s[0]!=t[0]);
	for(int i=0; i<n; ++i) {
		++cnt[x-y];
		k+=(x>=y);
		ans+=x>y?x-y:y-x;
		x+=s[i+1]!=s[i];
		y+=t[i+1]!=t[i];
	}
	if(2*k-n+cnt[-1]<0)
		for(int i=-1, d; (d=4*k-2*n+2*cnt[i])<0; i-=2) ans+=d, k+=cnt[i]+cnt[i-1];
	else
		for(int i=0, d; (d=2*n-4*k+4*cnt[i]+2*cnt[i+1])<0; i+=2) ans+=d, k-=cnt[i]+cnt[i+1];
	printf("%lld\n", ans);
	return 0;
}
