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<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long Int;

Int n;
vector<Int> read01(Int n){
  char last = '0';
  char c;
  vector<Int> hoge;
  for(Int i = 0;i < 2*n;i++)hoge.push_back(0);
  for(Int i = 0;i < n;i++){
    cin >> c;
    if(c!= last){
      hoge.push_back(i);
      last = c;
    }
  }
  for(Int i = 0;i < 2*n;i++)hoge.push_back(n);
  return hoge;
}

Int solve(vector<Int> &pos1, vector<Int> &pos2, Int offset){
  Int ans = 0;
  for(Int i = 0;i + offset < pos1.size() && i < pos2.size();i++){
    ans += abs(pos1[offset+i] - pos2[i]);
  }
  return ans;
}

int main(){
  cin >> n;
  vector<Int> pos1 = read01(n);
  vector<Int> pos2 = read01(n);
  Int res = 1LL << 60;
  for(Int i = 0;i < 2*n;i+=2){
    res = min(res, solve(pos1, pos2, i));
    res = min(res, solve(pos2, pos1, i));
  }
  cout << res << endl;
  return 0;
}