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
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 5010
int len;
char s[N],t[N];
int n,m,a[N],b[N];
int main(){
	scanf("%d%s%s",&len,s+1,t+1);
	for (int i=1;i<=len;++i){
		if (s[i]!=s[i+1])
			a[++n]=i;
		if (t[i]!=t[i+1])
			b[++m]=i;
	}
	int ans=0,res=0;
	for (int i=1;i<=n;++i)
		res+=a[i];
	for (int j=1;j<=m;++j)
		res+=len-b[j];
	ans=res;
	res=0;
	for (int i=1;i<=n;++i)
		res+=len-a[i];
	for (int j=1;j<=m;++j)
		res+=b[j];
	ans=min(ans,res);
	if (n>=1){
		for (int j=1;j<=m;++j){
			if (s[a[1]]!=t[b[j]])
				continue;
			int res=0,k=1;
			for (;k<j;++k)
				res+=b[k];
			for (;k<=m && k-j+1<=n;++k)
				res+=abs(b[k]-a[k-j+1]);
			if (k-j+1<=n)
				for (;k-j+1<=n;++k)
					res+=len-a[k-j+1];
			else
				for (;k<=m;++k)
					res+=len-b[k];
			ans=min(ans,res);
		}
	}
	if (m>=1){
		for (int i=1;i<=n;++i){	
			if (s[a[i]]!=t[b[1]])	
				continue;
			int res=0,k=1;
			for (;k<i;++k)
				res+=a[k];
			for (;k<=n && k-i+1<=m;++k)
				res+=abs(b[k-i+1]-a[k]);
			if (k-i+1<=m)
				for (;k-i+1<=m;++k)
					res+=len-b[k-i+1];
			else
				for (;k<=n;++k)
					res+=len-a[k];
			ans=min(ans,res);
		}
	}
	printf("%d\n",ans);
	return 0;
}













