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 <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define FILL(a, n, x) memset((a), (x), sizeof ((a)[0]) * (n))
#define COPY(a, n, b) memcpy((b), (a), sizeof ((a)[0]) * (n))
using namespace std;

typedef long long li;

// const int mod = 1e9 + 7, inv2 = mod + 1 >> 1;
// inline int Add(int x) { return x >= mod ? x - mod : x; }
// inline void Add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
// inline int Sub(int x) { return x < 0 ? x + mod : x; }
// inline void Sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
// inline int Mul(int x, int y) { return (li)x * y % mod; }

// int Pow(int x, int y) {
//   int z = 1;
//   for (; y; y >>= 1) {
//     if (y & 1) z = Mul(z, x);
//     x = Mul(x, x);
//   }
//   return z;
// }

// ----------------------------------------

const int maxn = 5000;

int n;
char s[maxn + 1], t[maxn + 1];
vector<int> a, b;

int Get(vector<int> &a, int i) {
  if (i < 0) return 0;
  if (i >= a.size()) return n;
  return a[i];
}

int main(void) {
  scanf("%d%s%s", &n, s, t);
  for (int i = 0; i < n - 1; ++i) if (s[i] != s[i + 1]) a.push_back(i + 1);
  for (int i = 0; i < n - 1; ++i) if (t[i] != t[i + 1]) b.push_back(i + 1);
  int best = 1e9;
  int odd = (s[0] != t[0]);
  for (int d = -n; d <= n; ++d) {
    if (odd + d & 1) continue;
    int ans = 0;
    for (int i = -n; i < 2 * n; ++i) {
      ans += abs(Get(a, i) - Get(b, i + d));
    }
    best = min(best, ans);
  }
  printf("%d\n", best);
  return 0;
}
