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;

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n;
  string s, t;
  cin >> n >> s >> t;
  if (n <= 2) {
    int answer = 0;
    for (int i = 0; i < n; ++i) {
      if (s[i] != t[i]) {
        ++answer;
      }
    }
    printf("%d\n", answer);
    return 0;
  }
  vector<pair<int, int>> diff_s, diff_t;
  for (int i = 0; i < n - 1; ++i) {
    if (s[i] != s[i + 1]) {
      diff_s.emplace_back(i, s[i] - '0');
    }
    if (t[i] != t[i + 1]) {
      diff_t.emplace_back(i, t[i] - '0');
    }
  }
  int answer = INT_MAX;
  auto solve = [&](vector<pair<int, int>> a, vector<pair<int, int>> b) {
    if (a.size() > b.size()) {
      swap(a, b);
    }
    reverse(a.begin(), a.end());
    while (a.size() < b.size()) {
      a.emplace_back(-1, !a.back().second);
    }
    reverse(a.begin(), a.end());
    if (a.back().second == b.back().second) {
      int result = 0;
      for (int i = 0; i < a.size(); ++i) {
        result += abs(a[i].first - b[i].first);
      }
      answer = min(answer, result);
    }
  };
  for (int rotate = 0; rotate < 2; ++rotate) {
    vector<pair<int, int>> new_diff_t = diff_t;
    for (int i = 0; i <= n; ++i) {
      solve(diff_s, new_diff_t);
      new_diff_t.emplace_back(n - 1, !new_diff_t.back().second);
    }
    swap(diff_s, diff_t);
  }
  printf("%d\n", answer);
  return 0;
}
