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 = 5000;

int n;
bool a[N + 5], b[N + 5];
char s[N + 5], t[N + 5];

int main() {
  scanf("%d%s%s", &n, s, t);

  if (n <= 2) {
      printf("%d\n", (s[0] != t[0]) + (s[1] != t[1]));
      return 0;
  }

  for (int i = 1; i < n; ++i) {
    a[i] = s[i] != s[i-1];
    b[i] = t[i] != t[i-1];
  }

  int ans = 0x3f3f3f3f;
  bool flag = s[0] != t[0];

  for (int i = flag; i < n; i += 2) {
    int res = 0;
    vector<int> tmp;
    for (int j = n - 1; j > 0; --j) if(a[j] == 0) tmp.push_back(j);
    for (int j = 0; j < i; ++j) tmp.push_back(0);

    for (int j = 1; j < n; ++j) if(b[j] == 0) {
      if (tmp.size()) {
        res += abs(j - tmp.back());
        tmp.pop_back();
      } else {
        res += n - j;
      }
    }

    while(!tmp.empty()) {
      res += n - tmp.back();
      tmp.pop_back();
    }
    ans = min(ans, res);
  }
  
  swap(a, b);
  for (int i = flag; i < n; i += 2) {
    int res = 0;
    vector<int> tmp;
    for (int j = n - 1; j > 0; --j) if(a[j] == 0) tmp.push_back(j);
    for (int j = 0; j < i; ++j) tmp.push_back(0);

    for (int j = 1; j < n; ++j) if(b[j] == 0) {
      if (tmp.size()) {
        res += abs(j - tmp.back());
        tmp.pop_back();
      } else {
        res += n - j;
      }
    }

    while(!tmp.empty()) {
      res += n - tmp.back();
      tmp.pop_back();
    }
    ans = min(ans, res);
  }
  printf("%d\n", ans);
  return 0;
}
