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>

int n;
std::string s, t;

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n >> s >> t;
	if (n <= 2) {
		int a = 0; for (int i = 0; i < n; ++i) a += s[i] != t[i];
		return std::cout << a << '\n', 0;
	}

	std::vector<int> S, T; if (s < t) std::swap(s, t);

	if (s[0] == '1') S.emplace_back(0);
	for (int i = 1; i < n; ++i) if (s[i] != s[i - 1]) S.emplace_back(i);
	if (t[0] == '1') T.emplace_back(0);
	for (int i = 1; i < n; ++i) if (t[i] != t[i - 1]) T.emplace_back(i);

	if (S.size() < T.size()) std::swap(S, T);
	while (T.size() < S.size()) T.emplace_back(n);

	for (int i = 0; i < n / 2; ++i) S.insert(S.begin(), 0), T.insert(T.begin(), 0);
	for (int i = 0; i < n / 2; ++i) S.emplace_back(n), T.emplace_back(n);

	// for (int i : S) std::cout << i << ' '; std::cout << std::endl;
	// for (int j : T) std::cout << j << ' '; std::cout << std::endl;

	int ans = 0x3f3f3f3f3f;
	for (int i = -int(T.size()) >> 1 << 1; i < (int) T.size(); i += 2) {
		// S[0] -> T[i]
		int sum = 0;
		for (int j = 0; j < T.size(); ++j) {
			int k = j - i, p;
			if (k < 0) p = 0;
			else if (k >= S.size()) p = n;
			else p = S[k];
			// std::cout << "match : " << T[j] << ' ' << p << ' ' << k << std::endl;
			sum += std::abs(T[j] - p);
		}
		// std::cout << i << ' ' << sum << std::endl;
		ans = std::min(ans, sum);
	}

	std::cout << ans << '\n';

	return 0;
}