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 N = 5010;
int n, ans = 0;
char s[N], t[N];
vector<int> a, b;
int check(int x, int y) {
  int i = 0, j = 0, ret = 0;
  while (i < x) ret += a[i++];
  while (j < y) ret += b[j++];
  while (i < (int) a.size() && j < (int) b.size()) ret += abs(a[i++] - b[j++]);
  while (i < (int) a.size()) ret += n - a[i++];
  while (j < (int) b.size()) ret += n - b[j++];
  return ret;
}
int main() {
  scanf("%d%s%s", &n, s + 1, t + 1);
  s[0] = t[0] = '0';
  for (int i = 0; i < n; i++) {
    if (s[i + 1] != s[i]) a.push_back(i);
    if (t[i + 1] != t[i]) b.push_back(i);
  }
  for (int i = 0; i < (int) a.size(); i += 2) {
    if (i + 1 < (int) a.size()) ans += min(a[i] + a[i + 1], n - a[i] + n - a[i + 1]);
    else ans += n - a[i];
  }
  for (int j = 0; j < (int) b.size(); j += 2) {
    if (j + 1 < (int) b.size()) ans += min(b[j] + b[j + 1], n - b[j] + n - b[j + 1]);
    else ans += n - b[j];
  }
  for (int i = 0; i < (int) a.size(); i += 2) {
    for (int j = 0; j < (i ? 1 : (int) b.size()); j += 2) {
      ans = min(ans, check(i, j));
    }
  }
  printf("%d\n", ans);
}
