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 <algorithm>
#include <vector>
const int MAXN = 5000 + 10;

int n;
char s[MAXN], t[MAXN];
std::vector <int> pos1, pos2;
int main() {
  scanf("%d%s%s", &n, s + 1, t + 1);

  pos1.push_back(0);
  pos2.push_back(0);
  for (int i = 1; i < n; i++) {
    if (s[i] != s[i + 1]) pos1.push_back(i);
    if (t[i] != t[i + 1]) pos2.push_back(i);
  }
  pos1.push_back(n);
  pos2.push_back(n);

  int ans = 1e9;

  for (int i = (n & 1) == (s[1] == t[1]) ? -n - 1 : -n; i <= n + 1; i += 2) {
    int tot = 0;
    for (int j = 0; j < (int) pos1.size(); j++) {
      int x = i + j;
      if (x < 0) tot += pos1[j];
      else if (x >= (int) pos2.size()) tot += n - pos1[j];
      else tot += std::abs(pos2[x] - pos1[j]);
    }
    for (int j = 0; j < (int) pos2.size(); j++) {
      int x = j - i;
      if (x < 0) tot += pos2[j];
      else if (x >= (int) pos1.size()) tot += n - pos2[j];
    }
    
    // fprintf(stderr, "%d %d\n", i, tot);
    ans = std::min(ans, tot);
  }
  printf("%d\n", ans);
}
