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;

vector<pair<int,int> > vec1,vec2;
int n;
char str1[5050],str2[5050]; 

int main()
{
	scanf("%d %s %s",&n,str1 + 1,str2 + 1);
	for(int i = 1;i <= n; ++ i) vec1.push_back(make_pair(i & 1,0));
	if((n & 1) != str1[1] - '0') vec1.push_back(make_pair(str1[1] - '0',0));
	for(int i = 1;i <= n; ++ i)
		if(str1[i] != str1[i + 1]) vec1.push_back(make_pair((str1[i] - '0') ^ 1,i));
	for(int i = 1;i <= n; ++ i)
		vec1.push_back(make_pair(vec1[vec1.size() - 1].first ^ 1,n));
	vec2.push_back(make_pair(str2[1] - '0',0));
	for(int i = 1;i <= n; ++ i)
		if(str2[i] != str2[i + 1])
			vec2.push_back(make_pair((str2[i] - '0') ^ 1,i));
	int sz = vec2.size(),ans = 0x3f3f3f3f;
	for(int i = 0;i + sz - 1 < vec1.size(); ++ i)
	{
		int tmp = 0;
		if(vec2[0].first != vec1[i].first) continue;
		for(int j = 1;j <= sz; ++ j)
			tmp += abs(vec1[i + j - 1].second - vec2[j - 1].second);
		for(int j = 0;j < i; ++ j)
			tmp += vec1[j].second;
		for(int j = i + sz;j < vec1.size(); ++ j)
			tmp += n - vec1[j].second;
		ans = min(ans,tmp);
	}
	printf("%d\n",ans);
}