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>
#define int long long
using namespace std;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<pair<int, int> > lines;
    for (int i=0; i < 3*n; i++){
        lines.push_back({0, 0});
        lines.push_back({0, 1});
    }
    if (s[0] != '0') lines.push_back({0, 0});
    for (int i=0; i < n-1; i++){
        if (s[i] != s[i+1]){
            lines.push_back({i+1, s[i] - '0'});
        }
    }
    if (s[s.size() - 1] == '1') lines.push_back({n, 1});
    for (int i=0; i < 3*n; i++){
        lines.push_back({n, 0});
        lines.push_back({n, 1});
    }
    string t;
    cin >> t;
    vector<pair<int, int> > lw;
    for (int i=0; i < n; i++){
        lw.push_back({0, 0});
        lw.push_back({0, 1});
    }
    if (t[0] != '0') lw.push_back({0, 0});
    for (int i=0; i < n-1; i++){
        if (t[i] != t[i+1]){
            lw.push_back({i+1, t[i] - '0'});
        }
    }
    if (t[t.size() - 1] == '1') lw.push_back({n, 1});
    for (int i=0; i < n; i++){
        lw.push_back({n, 0});
        lw.push_back({n, 1});
    }
    int ans = 1e18;
    //for (int i=0; i < lines.size();i++) cout << lines[i].first << " " << lines[i].second << endl;
    for (int i=0; i <= lines.size()-lw.size();i++){
        int tet=0;
        if (lines[i].second != lw[0].second) continue;
        for (int j=0; j < lw.size(); j++) tet += abs(lw[j].first - lines[i+j].first);
        ans = min(ans, tet);
        //cout << i << " " << tet << endl;
    }
    cout << ans;
    return 0;
}

