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 mo 1000000007
#define ny 499122177
#define maxn 1000000000000000000LL
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1; 
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long n,i,j,book[20005],top,book2[20005],top2,ans,min1,sum[20005];
char s[5005],t[5005];
int main(){
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	n=read();
	scanf("%s",s+1);
	scanf("%s",t+1);
	
	for(i=1;i<n;i++)
		if(t[i]!=t[i+1]){
			top++;
			book[top]=i;
		}
	
	for(i=1;i<n;i++)
		if(s[i]!=s[i+1]){
			top2++;
			book2[top2]=i;
		}
	
	if(top>top2){
		swap(top,top2);
		swap(book,book2);
	}
	for(i=n+top2;i>=n+1;i--)
		book2[i]=book2[i-n];
	for(i=1;i<=n;i++)
		book2[i]=0;
	for(i=n+top2+1;i<=n*2+top2;i++)
		book2[i]=n;
	for(i=1;i<=n*2+top2;i++)
		sum[i]=sum[i-1]+book2[i];
	min1=maxn;
	for(i=(t[1]!=s[1])^(n&1);i<=n+top2;i+=2){
		ans=sum[i]+n*(n*2+top2-i-top)-(sum[n*2+top2]-sum[i+top]);
		for(j=1;j<=top;j++)
			ans+=abs(book2[i+j]-book[j]);
		min1=min(min1,ans);
	}
	pus(min1,2);
  	return 0;
}