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>

using namespace std;

const int MX = 5005;

int n;
char str[MX], tar[MX];

void input()
{
	scanf("%d", &n);
	scanf("%s", str+1);
	scanf("%s", tar+1);
}

vector<int> get_seq(char *s)
{
	vector<int> ret;
	for(int i=1; i<=n+1; i++)
		if(s[i] != s[i-1])
			ret.push_back(i);
	return ret;
}

int calc(vector<int> a, vector<int> b)
{
	int ret = 0;
	for(int i=1; i<=a.size()||i<=b.size(); i++)
	{
		int va = (i>a.size()) ? 1 : a[a.size()-i];
		int vb = (i>b.size()) ? 1 : b[b.size()-i];
		ret += abs(va-vb);
	}
	return ret;
}

void work()
{
	int ans = 1e9;
	vector<int> s0 = get_seq(str), t0 = get_seq(tar), s, t;
	for(int i=(str[n]!=tar[n]); i<=s0.size(); i+=2)
	{
		s = s0, t = t0;
		for(int j=1; j<=i; j++) s.push_back(n+1);
		ans = min(calc(s, t), ans);

		s = s0, t = t0;
		int tmp = 0;
		for(int j=1; j<=i; j++) tmp += abs(n+1-s.back()), s.pop_back();
		ans = min(calc(s, t)+tmp, ans);
	}
	printf("%d\n", ans);
}

int main()
{
	input();
	work();
	return 0;
}