A. Neko Finds Grapes

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

On a random day, Neko found nn treasure chests and mm keys. The ii-th chest has an integer aiai written on it and the jj-th key has an integer bjbj on it. Neko knows those chests contain the powerful mysterious green Grapes, thus Neko wants to open as many treasure chests as possible.

The jj-th key can be used to unlock the ii-th chest if and only if the sum of the key number and the chest number is an odd number. Formally, ai+bj≡1(mod2)ai+bj≡1(mod2). One key can be used to open at most one chest, and one chest can be opened at most once.

Find the maximum number of chests Neko can open.

Input

The first line contains integers nn and mm (1≤n,m≤1051≤n,m≤105) — the number of chests and the number of keys.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the numbers written on the treasure chests.

The third line contains mm integers b1,b2,…,bmb1,b2,…,bm (1≤bi≤1091≤bi≤109) — the numbers written on the keys.

Output

Print the maximum number of chests you can open.

Examples

input

Copy

5 4
9 14 6 2 11
8 4 7 20

output

Copy

3

input

Copy

5 1
2 4 6 8 10
5

output

Copy

1

input

Copy

1 4
10
20 30 40 50

output

Copy

0

Note

In the first example, one possible way to unlock 33 chests is as follows:

• Use first key to unlock the fifth chest,
• Use third key to unlock the second chest,
• Use fourth key to unlock the first chest.

In the second example, you can use the only key to unlock any single chest (note that one key can't be used twice).

In the third example, no key can unlock the given chest.

解题说明：此题是一道模拟题，找出每组的奇数个数和偶数个数，则答案为第一组的奇数个数和第二组偶数个数的最小值加上第一组的偶数个数和第二组奇数数个数的最小值（要想得到奇数，必须是奇数加偶数）

 

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;


int n, m, a, i, l1, l2;
int main()
{
	cin >> n >> m;
	for (i = 1; i <= n; i++)
	{
		cin >> a;
		if (a % 2 == 0)
		{
			l1++;
		}
	}

	for (i = 1; i <= m; i++)
	{
		cin >> a;
		if (a % 2 == 0)
		{
			l2++;
		}
	}

	cout << min(l1, m - l2) + min(l2, n - l1);
	return 0;
}