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 <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e5+5;
char S[N],T[N];
int n,ans=1e9,cnt1,cnt2,A[N],B[N],tmpA[N],tmpB[N];

template <typename _Tp> inline void IN(_Tp&x) {
	char ch;bool flag=0;x=0;
	while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	if(flag) x=-x;
}

int main() {
	IN(n),scanf("%s%s",S+1,T+1);
	cnt1=(bool)(S[1]=='1'),cnt2=(bool)(T[1]=='1');
	for(int i=1;i<n;++i)
		(S[i]!=S[i+1])?tmpA[++cnt1]=i:0,(T[i]!=T[i+1])?tmpB[++cnt2]=i:0;
	(S[n]=='1')?tmpA[++cnt1]=n:0,(T[n]=='1')?tmpB[++cnt2]=n:0;
	int lim=cnt1+cnt2+cnt2;
	for(int i=cnt2+1;i<=lim;++i) A[i]=(i<=cnt1+cnt2)?tmpA[i-cnt2]:n;
	for(int i=0;i<=cnt1+cnt2;i+=2) {
		int res=0;
		for(int j=1;j<=lim;++j) B[j]=j<=i?0:(j<=i+cnt2?tmpB[j-i]:n);
		for(int j=1;j<=lim;++j) res+=abs(A[j]-B[j]);
		ans=min(ans,res);
	}
	return printf("%d\n",ans),0;
}