Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Neko Finds Grapes

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOn a random day, Neko found $$$n$$$ treasure chests and $$$m$$$ keys. The $$$i$$$-th chest has an integer $$$a_i$$$ written on it and the $$$j$$$-th key has an integer $$$b_j$$$ on it. Neko knows those chests contain the powerful mysterious green Grapes, thus Neko wants to open as many treasure chests as possible.

The $$$j$$$-th key can be used to unlock the $$$i$$$-th chest if and only if the sum of the key number and the chest number is an odd number. Formally, $$$a_i + b_j \equiv 1 \pmod{2}$$$. 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 $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) — the number of chests and the number of keys.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the numbers written on the treasure chests.

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$) — the numbers written on the keys.

Output

Print the maximum number of chests you can open.

Examples

Input

5 4 9 14 6 2 11 8 4 7 20

Output

3

Input

5 1 2 4 6 8 10 5

Output

1

Input

1 4 10 20 30 40 50

Output

0

Note

In the first example, one possible way to unlock $$$3$$$ 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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/20/2021 15:13:34 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|