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()
{
  do {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  } while (false);
  int n;
  string s, t;
  cin >> n >> s >> t;
  auto parse = [&] (string & str) {
    vector<int> res;
    for (int i = 1; i < str.size(); i++) {
      if (str[i] != str[i - 1]) {
        res.push_back(i);
      }
    }
    return res;
  };
  vector<int> a = parse(s), b = parse(t);
  int ans = INT_MAX, na = a.size(), nb = b.size();
  for (int i = -na - 1; i <= nb + 1; i++) {
    if ((i & 1) != (s[0] == t[0])) {
      int sum = 0;
      for (int j = min(-i, 0); j < max(na, nb - i); j++) {
        auto calc = [&] (vector<int> &x, int p) {
          return p < 0 ? 0 : p >= x.size() ? n : x[p];
        };
        sum += abs(calc(a, j) - calc(b, j + i));
      }
      ans = min(ans, sum);
    }
  }
  cout << ans << endl;
  return 0;
}
