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 = 5005;

char s[N], t[N];
vector <int> A[2], B[2];
int n;

int solve(vector <int> a, vector <int> b) {
  if(a.size() < b.size()) swap(a, b);
  int ans = 2e9;
  for(int bef = 0; bef <= a.size(); ++ bef) {
    int res = 0;
    vector <int> A, B; A.clear(); B.clear();
    for(int j = 1; j <= bef; ++ j) B.push_back(0);
    for(int j = 0; j < (int) b.size(); ++ j) B.push_back(b[j]);
    A = a;
    while(A.size() < B.size()) A.push_back(n);
    while(B.size() < A.size()) B.push_back(n);
    for(int j = 0; j < (int) A.size(); ++ j)
      res += abs(A[j] - B[j]);
    ans = min(ans, res);
  }

  for(int bef = 0; bef <= a.size(); ++ bef) {
    int res = 0;
    vector <int> A, B; A.clear(); B.clear();
    for(int j = 1; j <= bef; ++ j) A.push_back(0);
    for(int j = 0; j < (int) a.size(); ++ j) A.push_back(a[j]);
    B = b;
    while(A.size() < B.size()) A.push_back(n);
    while(B.size() < A.size()) B.push_back(n);
    for(int j = 0; j < (int) A.size(); ++ j)
      res += abs(A[j] - B[j]);
    ans = min(ans, res);
  }
  
  return ans;
}

int main() {
  cin >> n;
  scanf("%s", s + 1);
  scanf("%s", t + 1);
  for(int i = 1; i <= n; ++ i) s[i] -= '0', t[i] -= '0';
  for(int i = 1; i < n; ++ i) {
    if(s[i] ^ s[i + 1]) A[s[i]].push_back(i);
    if(t[i] ^ t[i + 1]) B[t[i]].push_back(i);
  }
  if(n <= 2) {
    int ans = 0;
    for(int i = 1; i <= n; ++ i) ans += (s[i] != t[i]);
    cout << ans << endl;
    return 0;
  }
  int ans = 0;
  ans += solve(A[0], B[0]);
  ans += solve(A[1], B[1]);
  cout << ans << endl;
}
