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>
int N;
int dif(int a,int b){return a>b?a-b:b-a;}
int calc(int*s,int*t,int sl,int tl,int ty){
	int ans=1<<30;
	for(int i=ty;i<=sl;i+=2){
		int tmp=0;
		if(i+tl<=sl){
			tmp=sl-tl;
			for(int j=0;j<sl;j++)tmp+=j<i?s[j]:j<i+tl?dif(s[j],t[j-i]):N-s[j]-2;
		}
		else{
			tmp=i*2+tl-sl;
			for(int j=0;j<sl;j++)tmp+=j<i?s[j]:dif(s[j],t[j-i]);
			for(int j=sl-i;j<tl;j++)tmp+=N-t[j]-2;
		}
		if(tmp<ans)ans=tmp;
	}
	return ans;
}
int s[5010],t[5010],sl,tl;
char str[5010];
int main(){
	scanf("%d%s",&N,str);
	for(int i=0;i<N;i++)if(str[i]==str[i+1])s[sl++]=i;
	int ty=*str;
	scanf("%s",str);
	for(int i=0;i<N;i++)if(str[i]==str[i+1])t[tl++]=i;
	ty^=*str;
	int ans1=calc(s,t,sl,tl,ty),ans2=calc(t,s,tl,sl,ty),ans=ans1<ans2?ans1:ans2;
	if(ty&&!sl&&!tl)ans=N;
	printf("%d\n",ans);
}