Однажды Неко нашёл \(n\) сундуков с сокровищами и \(m\) ключей. На \(i\)-м сундуке было написано целое число \(a_i\), а на \(j\)-м ключе написано целое число \(b_j\). Неко знает, что эти сундуки содержат волшебный виноград удивительной магической силы, так что он хочет открыть как можно больше сундуков.
Как оказалось, \(j\)-й ключ может открыть \(i\)-й сундук если (и только если) сумма чисел на ключе и на сундуке является нечётным числом. Иначе говоря, \(a_i + b_j \equiv 1 \pmod{2}\). Один ключ может открыть не более одного сундука, а один сундук нельзя открыть более одного раза.
Выясните максимальное количество сундуков, которое можно открыть.
Выходные данные
Выведите одно число — максимальное количество сундуков, которое вы сможете открыть.
Примечание
В первом примере один из способов открыть \(3\) сундука выглядит следующим образом:
- Использовать первый ключ чтобы открыть пятый сундук,
- Использовать третий ключ, чтобы открыть второй сундук,
- Использовать четвёртый ключ, чтобы открыть первый сундук.
Во втором примере вы можете использовать единственный ключ, чтобы открыть один произвольный сундук (обратите внимание что один ключ нельзя использовать дважды).
В третьем примере ни один из ключей не поможет открыть сундук.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
9 14 6 2 11
8 4 7 20
|
3
|
|
2
|
5 1
2 4 6 8 10
5
|
1
|
|
3
|
1 4
10
20 30 40 50
|
0
|