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;

const int N = 5e3 + 10;

typedef pair<int, int> pi; 

int n;
string s, t;
vector<pi> S, T;

int main() {
  cin >> n >> s >> t;
  if (n <= 2) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
      if (s[i] != t[i]) ans++;
    }
    cout << ans << endl;
    return 0;
  }
  if (s[0] == '0') {
    for (int i = n; i >= 0; i--) S.push_back(pi(0, i & 1));
  } else {
    for (int i = n; i >= 1; i--) S.push_back(pi(0, i & 1));
  }
  for (int i = 1; i < n; i++) {
    if (s[i] == s[i - 1]) continue;
    S.push_back(pi(i, s[i] - '0'));
  }
  if (s[n - 1] == '0') {
    for (int i = 1; i <= n; i++) S.push_back(pi(n, i & 1));
  } else {
    for (int i = 0; i <= n; i++) S.push_back(pi(n, i & 1));
  }
  for (int i = 1; i < n; i++) {
    if (t[i] == t[i - 1]) continue;
    T.push_back(pi(i, t[i] - '0'));
  }
  int ans = n * n;
  for (int i = 0; i + T.size() - 1 < S.size(); i++) {
    if (S[i].second != T[0].second) continue;
    int cur = 0;
    for (int j = 0; j < S.size(); j++) {
      if (j < i) cur += abs(S[j].first);
      if (j > i + T.size() - 1) cur += abs(S[j].first - n); 
    }
    for (int j = 0; j < T.size(); j++) {
      cur += abs(S[i + j].first - T[j].first);
    }
    ans = min(ans, cur);
  }
  cout << ans << endl;
  return 0;
}
