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 re register
using namespace std;
char ss[10001001],tt[10001001];
int n,st[20001001],*h=st+10000001;
int main()
{
	re int x=0,y=0,x1=0;
	re long long ans=0;
	scanf("%d%s%s",&n,ss+1,tt+1);y=(ss[1]!=tt[1]);
	for(re int i=1;i<=n;i++)
	{
		h[x-y]++;x1+=(x>=y);ans+=(x>y)?x-y:y-x;
		if(ss[i]!=ss[i+1])x++;
		if(tt[i]!=tt[i+1])y++;
	}
	if(2*x1<n)
	for(re int i=-1;2*x1+h[i]<n;i-=2)
	{
		ans-=(n-2*x1-h[i])*2;x1+=h[i]+h[i-1];
	}else
	{
		x1-=h[0];
		for(re int i=1;2*x1>n+h[i];i+=2)
		{
			ans-=(2*x1-n-h[i])*2;x1-=h[i]+h[i+1];
		}
	}printf("%lld",ans);
}