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 <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int MAXN = 5005;

int n,tota,totb,ans;
int a[MAXN];
int b[MAXN];

string s,t;

int main()
{
	ios::sync_with_stdio(0);
	cin >> n >> s >> t;
	for (int i = 0;i < n - 1;i++)
		if (s[i] == s[i + 1])
			a[++tota] = i + 1;
	for (int i = 0;i < n - 1;i++)
		if (t[i] == t[i + 1])
			b[++totb] = i + 1;
	if (tota > totb)
	{
		swap(tota,totb);
		swap(a,b);
	}
	ans = 1e9;
	for (int st = -tota;st <= totb + 2;st++)
	{
		if ((~st & 1) != (s[0] != t[0]))
			continue;
		int l = min(1,st),r = max(st + tota - 1,totb),res = 0;
		for (int i = l;i <= r;i++)
		{
			int A = 0,B = 0;
			if (i >= st && i <= st + tota - 1)
				A = a[i - st + 1];
			else if (i > st + tota - 1)
				A = n;
			if (i >= 1 && i <= totb)
				B = b[i];
			else if (i > totb)
				B = n;
			res += abs(A - B);
		}
		ans = min(ans,res);
	}
	cout << ans << endl;
	return 0;
}