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
/**
 *    author:  tourist
 *    created: 29.12.2018 16:10:26       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<string> s(2);
  cin >> s[0] >> s[1];
  vector<int> groups(2);
  vector<vector<int>> twos(2);
  for (int q = 0; q < 2; q++) {
    int i = 0;
    while (i < n) {
      if (i < n - 1 && s[q][i] == s[q][i + 1]) {
        twos[q].push_back(groups[q]);
        groups[q]++;
        i += 2;
      } else {
        groups[q]++;
        i += 1;
      }
    }
  }
  int match = (s[0][0] == s[1][0]);
  if (twos[0].empty() && twos[1].empty()) {
    cout << (match ? 0 : n) << '\n';
    return 0;
  }
  int ans = (int) 1e9;
  for (int rot = 0; rot < 2; rot++) {
    for (int x = 0; x <= (int) twos[0].size(); x++) {
      if ((match ^ (x % 2)) == 0) {
        continue;
      }
      vector<int> t0 = twos[0];
      vector<int> t1 = twos[1];
      int new_0 = (int) t0.size() - x;
      int new_1 = (int) t1.size();
      int drop_0 = 0;
      int drop_1 = 0;
      if (new_0 > new_1) {
        drop_0 = new_0 - new_1;
      }          
      if (new_0 < new_1) {
        drop_1 = new_1 - new_0;
      }
      int cur = 0;
      int g0 = groups[0];
      int g1 = groups[1];
      for (int i = 0; i < drop_0; i++) {
        cur += g0 - t0.back();
        t0.pop_back();
        g0++;
      }
      for (int i = 0; i < drop_1; i++) {
        cur += g1 - t1.back();
        t1.pop_back();
        g1++;
      }
      for (int i = 0; i < x; i++) {
        cur += t0[i] + 1 + i;
        g0++;
      }
      assert(g0 == g1);
      for (int i = x; i < (int) t0.size(); i++) {
        t0[i] += x;
      }
      assert((int) t0.size() - x == (int) t1.size());
      for (int i = 0; i < (int) t0.size() - x; i++) {
        cur += abs(t0[i + x] - t1[i]);
      }
      ans = min(ans, cur);
    }
    swap(s[0], s[1]);
    swap(groups[0], groups[1]);
    swap(twos[0], twos[1]);
  }
  cout << ans << '\n';
  return 0;
}
