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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define fo(i,j,l) for(int i=j;i<=l;++i)
#define fd(i,j,l) for(int i=j;i>=l;--i)

using namespace std;
typedef long long ll;
const ll N=152e2;

int n,m;
char s[N],t[N];

int a[N][2],b[N][2];

inline int abs(int o)
{return (o<0)?(-o):o;}

inline int min(int a,int b)
{return a<b?a:b;}

int main()
{
	scanf("%d",&n);
	scanf("%s%s",s+1,t+1);
	int u=0,v=0;
	s[0]=t[0]='.';
	fo(i,1,n)if(s[i]!=s[i-1])a[++u][1]=s[i]^48,a[u][0]=i;
	fo(i,1,n)if(t[i]!=t[i-1])b[++v][1]=t[i]^48,b[v][0]=i;
	
	int ans=n*n*2;
	
	fo(i,0,n){
		int zd=max(i+u,v);
		int lj=0,ok=1;
		fo(l,1,zd){
			int po=(l<=v)?b[l][0]:n+1;
			int co=(l<=v)?b[l][1]:2;
			int _po=(l<=i)?1:((l>i+u)?n+1:a[l-i][0]);
			int _co=(l<=i)?2:((l>i+u)?2:a[l-i][1]);
			if(_co!=co&&co!=2&&_co!=2)ok=0;
			lj=lj+abs(po-_po);
		}
		if(ok)ans=min(ans,lj);
	}
	
	u=v=0;
	fo(i,1,n)swap(s[i],t[i]);
	fo(i,1,n)if(s[i]!=s[i-1])a[++u][1]=s[i]^48,a[u][0]=i;
	fo(i,1,n)if(t[i]!=t[i-1])b[++v][1]=t[i]^48,b[v][0]=i;
	
	fo(i,0,n){
		int zd=max(i+u,v);
		int lj=0,ok=1;
		fo(l,1,zd){
			int po=(l<=v)?b[l][0]:n+1;
			int co=(l<=v)?b[l][1]:2;
			int _po=(l<=i)?1:((l>i+u)?n+1:a[l-i][0]);
			int _co=(l<=i)?2:((l>i+u)?2:a[l-i][1]);
			if(_co!=co&&co!=2&&_co!=2)ok=0;
			lj=lj+abs(po-_po);
		}
		if(ok)ans=min(ans,lj);
	}
	
	cout<<ans;
}