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 cs const
#define pb push_back
using namespace std;
cs int N = 2e4 + 50;
int n; char S[N], T[N];
int A[N], B[N], ca, cb, a[N], b[N];
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d%s%s",&n,S+1,T+1);
	if(S[1]=='1') A[++ca]=0;
	for(int i=1; i<n; i++) if(S[i]!=S[i+1]) A[++ca]=i;
	if(S[n]=='1') A[++ca]=n;
	if(T[1]=='1') B[++cb]=0;
	for(int i=1; i<n; i++) if(T[i]!=T[i+1]) B[++cb]=i;
	if(T[n]=='1') B[++cb]=n;
	for(int i=1; i<=ca; i++) a[i+cb]=A[i];
	for(int i=ca+cb+1; i<=ca+cb+cb; i++) a[i]=n;
	int Ans=1e9;
	for(int i=0; i<=ca+cb; i+=2){
		for(int j=1; j<=i; j++) b[j]=0;
		for(int j=1; j<=cb; j++) b[i+j]=B[j];
		for(int j=i+cb+1; j<=ca+cb+cb; j++) b[j]=n;
		int now = 0;
		for(int j=1; j<=ca+cb+cb; j++) now += abs(b[j]-a[j]);
		Ans = min(Ans,now);
	} cout<<Ans; return 0;
}