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 <iostream>
#include <cstdio>
#define il inline
#define ri register
#define Size 5500
#define intmax 0x7fffffff
using namespace std;
bool a[Size],b[Size];
int A[Size],B[Size],at,bt;
il void get(char&);
int main(){
	int n;char c;scanf("%d",&n);
	for(int i(1);i<=n;++i)get(c),a[i]=c^48;
	for(int i(1);i<=n;++i)get(c),b[i]=c^48;
	for(int i(2);i<=n;++i){
		if(a[i]!=a[i-1])A[++at]=i-1;
		if(b[i]!=b[i-1])B[++bt]=i-1;
	}A[at+1]=B[bt+1]=n;
	int ans(intmax),beg(a[A[1]]==b[B[1]]?1:0);
	for(int i(beg-n-(n&1)),j,k,sum;i<=(beg+n+(n&1));i+=2){sum=0;
		for(j=(i<=0?1:2-i),k=(i<=0?i:1);j<=at||k<=bt;++j,++k){
			int u(j),v(k);
			if(u<0)u=0;if(u>at)u=at+1;
			if(v<0)v=0;if(v>bt)v=bt+1;
			sum+=abs(A[u]-B[v]);
		}ans=min(ans,sum);
	}printf("%d",ans);
	return 0;
}
il void get(char &c){
	while(c=getchar(),c==' '||c=='\n'||c=='\r');
}
