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 <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cassert>
#define SIZE 5005

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

char S[SIZE],T[SIZE];
vector <int> vx,vy;
int n;

ll score(int T)
{
	ll ret=0;
	for(int i=0;i<n;i++)
	{
		ret+=abs(vx[i]-vy[i]+2*T);
	}
	return ret;
}
int main()
{
	scanf("%d",&n);
	scanf("%s",&S);
	scanf("%s",&T);
	int now=0;
	for(int i=0;now<n;i++)
	{
		while(now<n&&S[now]-'0'==i%2) vx.push_back(i),now++;
	}
	now=0;
	for(int i=0;now<n;i++)
	{
		while(now<n&&T[now]-'0'==i%2) vy.push_back(i),now++;
	}
	int l=-n,r=n;
	while(r-l>1)
	{
		int d=(l+r+2*n)/2-n;
		if(score(d+1)-score(d)>=0) r=d;
		else l=d;
	}
	printf("%lld\n",min(score(l),score(r)));
	return 0;
}
