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;
#define int long long

int n;
string s, t;

vector<pair<int, int>> get_lines(string s) {
  vector<pair<int, int>> ans;
  ans.push_back(s[0] == '0' ? make_pair(0, 0) : make_pair(1, 0));
  for (int i = 1; i < n; ++i)
    if (s[i] != s[i - 1])
      ans.push_back({ans.back().first ^ 1, i});
  ans.push_back({ans.back().first ^ 1, n});
  return ans;
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> s >> t;
  vector<pair<int, int>> a = get_lines(s);
  vector<pair<int, int>> b = get_lines(t);
  reverse(b.begin(), b.end());
  for (int i = 0; i < 5005; ++i)
    b.push_back({b.back().first ^ 1, 0});
  reverse(b.begin(), b.end());
  for (int i = 0; i < 5005; ++i)
    b.push_back({b.back().first ^ 1, n});
  int ans = 2e9;
  for (int i = 0; i < b.size(); ++i) {
    if (b[i].first == a[0].first) {
      int x = 0, y = i;
      int cur = 0;
      while (y >= 0) {
        int u = 0, v = b[y].second;
        cur += v - u;
        --y;
      }
      x = 1, y = i + 1;
      while (y < b.size()) {
        int u = (x < a.size() ? a[x].second : n);
        int v = b[y].second;
        cur += abs(v - u);
        ++x;
        ++y;
      }
      ans = min(ans, cur);
    }
  }
  cout << ans << '\n';
  return 0;
}