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;
constexpr int INF = 1E9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s, t;
    cin >> n >> s >> t;
    vector<int> x {0}, y {0};
    for (int i = 1; i < n; ++i)
        if (s[i] != s[i - 1])
            x.push_back(i);
    for (int i = 1; i < n; ++i)
        if (t[i] != t[i - 1])
            y.push_back(i);
    x.push_back(n);
    y.push_back(n);
    int ans = INF;
    for (int i = -(int)x.size() + 1; i < (int)y.size(); ++i) {
        if ((i & 1) == (s[0] == t[0]))
            continue;
        int cnt = 0;
        for (int j = max(0, -i); j < min((int)y.size() - i, (int)x.size()); ++j)
            cnt += abs(x[j] - y[i + j]);
        for (int j = 0; j < -i; ++j)
            cnt += x[j];
        for (int j = (int)y.size() - i; j < (int)x.size(); ++j)
            cnt += n - x[j];
        for (int j = 0; j < i; ++j)
            cnt += y[j];
        for (int j = (int)x.size() + i; j < (int)y.size(); ++j)
            cnt += n - y[j];
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}