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>
#include<complex>
using namespace std;
typedef long long ll;

using namespace std;
#define N 10010
int NOEL(ll ans){
  cout<<ans<<endl;
  return 0;
}
vector<ll> x,y;
ll n;
int main(){
    string s,t;cin>>n>>s>>t;
    if(n==1)return NOEL(s!=t);
    if(n==2)return NOEL((s[0]!=t[0])+(s[1]!=t[1]));
    for(int i=1;i<n;i++){
      if(s[i]!=s[i-1])x.push_back(i);
      if(t[i]!=t[i-1])y.push_back(i);
    }
    ll ans=1e17;
    for(int k=-N;k<N;k++){
      if(k%2==0 xor t[y[0]]==s[x[0]])continue;
      ll cur=0;
      for(int i=-N;i<N;i++){
	int j=i+k; ll vx,vy;
	if(j<0)vx=0;
	else if(j>=x.size())vx=n;
	else vx=x[j];
	
	if(i<0)vy=0;
	else if(i>=y.size())vy=n;
	else vy=y[i];
	
	cur+=abs(vx-vy);
      }
      ans=min(ans,cur);
    }
    cout<<ans<<endl;
    return 0;
}
