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 llong long long
#define mkpr make_pair
#define riterator reverse_iterator
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int N = 5000;
char a[N+3],b[N+3];
int ta[N+3],tb[N+3];
int wa[3*N+7],wb[3*N+7];
int n,m1,m2;

int get_ta(int x) {return x>m1?n:ta[x];}
int get_tb(int x) {return x>m2?n:tb[x];}

int main()
{
	scanf("%d%s%s",&n,a+1,b+1);
	if(a[1]=='1') {ta[++m1] = 0;} for(int i=2; i<=n; i++) if(a[i]!=a[i-1]) {ta[++m1] = i-1;} if(a[n]=='1') {ta[++m1] = n;}
	if(b[1]=='1') {tb[++m2] = 0;} for(int i=2; i<=n; i++) if(b[i]!=b[i-1]) {tb[++m2] = i-1;} if(b[n]=='1') {tb[++m2] = n;}
	for(int i=m2+1; i<=m2+m1; i++) wa[i] = ta[i-m2];
	for(int i=1; i<=m2; i++) wa[i] = 0;
	for(int i=m2+m1+1; i<=m2+m1+m2; i++) wa[i] = n;
//	printf("wa: "); for(int i=1; i<=m2+m1+m2; i++) printf("%d ",wa[i]); puts("");
	int ans = 1e9;
	for(int i=0; i<=m1+m2; i+=2)
	{
		for(int j=1; j<=m2; j++) {wb[i+j] = tb[j];}
		for(int j=1; j<=i; j++) {wb[j] = 0;}
		for(int j=i+m2+1; j<=m1+m2+m2; j++) {wb[j] = n;}
		int cur = 0;
		for(int j=1; j<=m1+m2+m2; j++) {cur += abs(wa[j]-wb[j]);}
		ans = min(ans,cur);
	}
	printf("%d\n",ans);
	return 0;
}