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;

typedef pair <int, int> pii; 

const int N = 6000; 
const int INF = 1 << 30;

int n, lenS = 0, lenT = 0; 

pii s[N], t[N];
// <type, pos> 

string strS, strT;

inline void init_string( pii *a, string str, int &len )
{
	len = 0; int last = str[0] - '0'; 
	
	a[++len] = make_pair( last ^ 1, 0 ); 
	
	for( int i = 2; i <= n; i ++ )
	{
		if( last == str[i-1] - '0' ) continue;
		
		last ^= 1; 
		a[++len] = make_pair( last ^ 1, i - 1 ); 
	}
	
	a[++len] = make_pair( last, n ); 
} 

inline int calc_ans( int st )
{
	int ret = 0;

	// clear 1 -> st
	for( int i = 1; i < st; i ++ )
		ret += s[i].second; 

	for( int i = 1; i <= lenT; i ++ )
	{
		if( st < 1 ) {
			ret += t[i].second; st ++; continue;
		}
		
		if( st > lenS ) {
			ret += n - t[i].second; st ++; continue;
		}
		 
		if( t[i].first != s[st].first ) return INF;
		ret += abs( t[i].second - s[st].second ); 		
		st ++; 
	}
	
	// clear st -> n 
	for( int i = st; i <= lenS; i ++ )
		ret += n - s[i].second; 

	return ret;
}

int main()
{
//	freopen( "e.in", "r", stdin ); 
	
	cin >> n >> strS >> strT; 
	
	init_string( s, strS, lenS );
	init_string( t, strT, lenT );  

	int ans = INF;
	for( int i = 1 - lenT; i <= lenS; i ++ )
		ans = min( ans, calc_ans( i ) ) ;

	cout << ans << endl;

	return 0; 
}