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<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef pair<int, int>pii;
int get(pii a,pii b)
{
	if (a > b)swap(a, b);
	return b.second - a.second + b.first - a.first;
}
vector<pii>conv(string s)
{
	s.push_back('#');
	vector<pii>r;
	for (int i = 0; i < s.size() - 1; i++)
	{
		if (s[i] == '1')
		{
			if (s[i + 1] == '1')r.push_back(make_pair(i, i + 1)), i++;
			else r.push_back(make_pair(i, i));
		}
	}
	return r;
}
int solve(vector<pii>a, vector<pii>b, int num)
{
	//for (int i = 0; i < b.size(); i++)printf("%d %d  ", b[i].first, b[i].second); printf("\n");
	int mini = 1000000000;
	for (int p = 0; p <= b.size(); p++)
	{
		int s = 0;
		int l1 = -p, u1 = int(b.size() - p);
		int l2 = 0, u2 = a.size();
		for (int i = l1; i < max(u1, u2); i++)
		{
			bool f1 = l1 <= i&&i < u1, f2 = l2 <= i&&i < u2;
			if (f1)
			{
				if (f2)s += get(a[i], b[i + p]);
				else
				{
					if (i < l2)s += b[i + p].first + b[i + p].second + 1;
					else s += (num - 1 - b[i + p].first) + (num - 1 - b[i + p].second) + 1;
				}
			}
			else if (f2)s += (num - 1 - a[i].first) + (num - 1 - a[i].second) + 1;
		}
		//printf("%d %d\n", p, s);
		mini = min(mini, s);
	}
	return mini;
}
int main()
{
	int num;
	scanf("%d", &num);
	string s1, s2;
	cin >> s1 >> s2;
	vector<pii>v1 = conv(s1), v2 = conv(s2);
	int x = solve(v1, v2, num), y = solve(v2, v1, num);
	printf("%d\n", min(x, y));
}
