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 Rint register int
using namespace std;
const int N = 11111;
int n, n1, n2, ans, _a[N], _b[N], *a = _a + 5000, *b = _b + 5000;
char s1[N], s2[N];
int main(){
	scanf("%d%s%s", &n, s1 + 1, s2 + 1);
	if(s1[1] != s2[1]) a[++ n1] = 0;
	for(Rint i = 1;i < n;i ++){
		if(s1[i] != s1[i + 1]) a[++ n1] = i;
		if(s2[i] != s2[i + 1]) b[++ n2] = i;
	}
	for(Rint i = n1 + 1;i <= 5000;i ++) a[i] = n;
	for(Rint i = n2 + 1;i <= 5000;i ++) b[i] = n;
	ans = 1e9;
	for(Rint i = -n1;i <= n2;i ++) if(!(i & 1)){
		int tmp = 0;
		for(Rint j = -5000;j <= 5000;j ++)
			if(i + j >= -5000 && i + j <= 5000) tmp += abs(a[i + j] - b[j]);
			else {
				if(i + j < -5000) tmp += b[j];
				else tmp += n - b[j];
			}
		ans = min(ans, tmp);
	}
	printf("%d", ans);
}