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;

namespace TYC
{
	const int N = 5005 * 3;

	int n, A[N], B[N];
	char S[N], T[N];	

	inline int calc(const char c)
	{
		int ac = 0, bc = 0, ans = 0x3f3f3f3f;
		for (int i = 1; i < n; i++)
			if (S[i] == c && S[i + 1] != c)
				A[++ac] = i;
		for (int i = 1; i <= n; i++)
			B[++bc] = 0;
		for (int i = 1; i < n; i++)
			if (T[i] == c && T[i + 1] != c)
				B[++bc] = i;
		for (int i = 1; i <= n; i++)
			B[++bc] = n;
		for (int i = 1; i + ac - 1 <= bc; i++)
		{
			int v = 0;
			for (int j = 1; j <= ac; j++)
				v += abs(A[j] - B[i + j - 1]);
			for (int j = 1; j < i; j++)
				v += B[j];
			for (int j = i + ac; j <= bc; j++)
				v += n - B[j];
			ans = min(ans, v);
		}
		return ans;
	}

	void work()
	{
		scanf("%d%s%s", &n, S + 1, T + 1);
		if (n <= 2)
		{
			int ans = 0;
			for (int i = 1; i <= n; i++)
				ans += S[i] != T[i];
			printf("%d\n", ans);
		}
		else
			printf("%d\n", calc('0') + calc('1'));
	}
}

int main()
{
	TYC::work();
	return 0;
}