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;
inline void chmin (int& a, int b) {
  if (a > b) a = b;
}
int main() {
  int n;
  string s, t;
  cin >> n >> s >> t;
  vector<int> a, b;
  int pty;
  for (int i = 1; i < n; i++) {
    if (s[i] != s[i - 1]) a.emplace_back(i);
    if (t[i] != t[i - 1]) b.emplace_back(i);
  }
  if (a.empty() || b.empty()) {
    int ret = 0;
    for (int i = 0; i < n; i++) {
      if (s[i] != t[i]) ret++;
    }
    cout << ret << endl;
    return 0;
  } else {
    int pty = s[a[0]] != t[b[0]];
    int sz = a.size();
    int tz = b.size();
    int ret = 1e9;
    for (int d = -(sz + ((sz & 1) != pty)); d <= (tz + ((tz & 1) != pty)); d += 2) {
      int tmp = 0;
      for (int i = min(0, -d); i < max(sz, tz - d); i++) {
        int x;
        if (i < 0) {
          x = 0;
        } else if (i < sz) {
          x = a[i];
        } else {
          x = n;
        }
        int j = i + d;
        int y;
        if (j < 0) {
          y = 0;
        } else if (j < tz) {
          y = b[j];
        } else {
          y = n;
        }
        tmp += abs(x - y);
      }
      chmin(ret, tmp);
    }
    cout << ret << '\n';
  }
  return 0;
}