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 <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
 
#include <algorithm>
#include <tuple>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>
 
#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}
 
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int n;

int dist(const vector<int>& a, const vector<int>& b) {
  int ret = 0;
  for (int i = 0; i < a.size(); ++i) ret += abs(a[i] - b[i]);
  return ret;
}

int calc(vector<int> a, vector<int> b) {
  if (a.size() < b.size()) swap(a, b);
  int ans = 1 << 30;
  int x = a.size() - b.size();
  vector<int> tmpb = b, tmpa = a;
  for (int rep = 0; rep < x; ++rep) b.push_back(n);
  ans = dist(a, b);
  for (int rep = 2; rep <= x; rep += 2) {
    b.pop_back(); b.pop_back();
    b.insert(b.begin(), 0); b.insert(b.begin(), 0);
    ans = min(ans, dist(a, b));
  }
  b = tmpb; a = tmpa;
  for (int rep = 0; rep < x; ++rep) b.push_back(n);
  ans = min(ans, dist(a, b));
  for (int rep = 2; rep <= n; ++rep) {
    b.push_back(n); b.push_back(n);
    a.insert(a.begin(), 0); a.insert(a.begin(), 0);
    ans = min(ans, dist(a, b));
  }
  b = tmpb; a = tmpa;
  if (x & 1) {
    ++x;
    a.push_back(n);
  }
  for (int rep = 0; rep < x; ++rep) b.insert(b.begin(), 0);
  ans = min(ans, dist(a, b));
  for (int rep = 2; rep <= n; ++rep) {
    b.insert(b.begin(), 0); b.insert(b.begin(), 0);
    a.push_back(n); a.push_back(n);
    ans = min(ans, dist(a, b));
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s, t;
  cin >> n >> s >> t;
  vector<int> a, b;
  for (int i = 1; i < n; ++i) if (s[i] != s[i - 1]) a.push_back(i);
  for (int i = 1; i < n; ++i) if (t[i] != t[i - 1]) b.push_back(i);
  int ans = 1 << 30;
  if (s[0] != t[0]) {
    a.insert(a.begin(), 0); ans = min(ans, calc(a, b)); a.erase(a.begin());
    b.insert(b.begin(), 0); ans = min(ans, calc(a, b)); b.erase(b.begin());
  } else ans = calc(a, b);

  cout << ans;

  return 0;
}
