On 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.

Difficulty: interview

Starter code:

Solutions:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
k1 = 0
k2 = 0
for x in a:
    if x % 2 == 0:
        k1 += 1
    else:
        k2 += 1
m1 = 0
m2 = 0
for x in b:
    if x % 2 == 0:
        m1 += 1
    else:
        m2 += 1
print(min(k1, m2) + min(k2, m1))


n, m = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

Ao = 0
Bo = 0
for a in A:
    if a % 2 == 1:
        Ao += 1

for b in B:
    if b % 2 == 1:
        Bo += 1
Ae = n - Ao
Be = m - Bo

ans = min(Ao, Be) + min(Ae, Bo)

print(ans)

n,m=map(int,input().split())
l1=list(map(int,input().split()))
l2=list(map(int,input().split()))
x1=0
x2=0
y1=0
y2=0
for item in l1:
    if item%2==0:
        x1+=1
    else :
        x2+=1
for item in l2:
    if item%2==0:
        y1+=1
    else :
        y2+=1
print( min(x2,y1)+min(x1,y2))

def mp():
    return map(int, input().split())

n, m = mp()
a = list(mp())
b = list(mp())

n1 = n2 = c1 = c2 = 0
for i in a:
    if i % 2 == 0:
        c1 += 1
    else:
        n1 += 1
for i in b:
    if i % 2 == 0:
        c2 += 1
    else:
        n2 += 1
print(min(c1, n2) + min(c2, n1))

ii = lambda: int(input())
mi = lambda: list(map(int, input().split()))
li = lambda: list(mi())

n, m = mi()
a = li()
b = li()
a = [x % 2 for x in a]
b = [x % 2 for x in b]
ans = min(a.count(0), b.count(1)) + min(a.count(1), b.count(0))
print(ans)


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    odd = 0
    even = 0
    for i in range(n):
        if a[i] & 1:
            odd += 1
        else:
            even += 1
    b = list(map(int, input().split()))
    ans = 0
    for i in range(m):
        if b[i] & 1:
            if even:
                even -= 1
                ans += 1
        else:
            if odd:
                odd -= 1
                ans += 1
    print(ans)
    return 0

main()

n,m = list(map(int,input().split()))
chests = list(map(int,input().split()))
keys = list(map(int,input().split()))

even_chests = sum((x+1)%2 for x in chests)
odd_chests = sum((x)%2 for x in chests)
even_keys = sum((x+1)%2 for x in keys)
odd_keys = sum((x)%2 for x in keys)
print(min(even_chests,odd_keys)+min(odd_chests,even_keys))


n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))

a_odd, a_even, b_odd, b_even = 0,0,0,0

for i in a:
    if i % 2 == 0:
        a_even += 1
    else:
        a_odd += 1

for i in b:
    if i % 2 == 0:
        b_even += 1
    else:
        b_odd += 1

print(min(a_odd, b_even) + min(a_even, b_odd))


n,m=map(int,input().split())
a=[int(s) for s in input().split()]
b=[int(s) for s in input().split()]
cnt=0
cnt1=0
for i in range(n):
    if a[i]%2==0:
        cnt+=1
for i in range(m):
    if b[i]%2==0:
        cnt1+=1
print(min(cnt,m-cnt1)+min(cnt1,n-cnt))

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
chet_a = 0
nech_a = 0
chet_b = 0
nech_b = 0
for i in range(n):
    if a[i] % 2 == 0:
        chet_a += 1
    else:
        nech_a += 1
for i in range(m):
    if b[i] % 2 == 0:
        chet_b += 1
    else:
        nech_b += 1
print(min(chet_a, nech_b) + min(nech_a, chet_b))

n,m=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
ac=bc=0
for item in a:
    if item%2==0:
        bc+=1
for item in b:
    if item%2==0:
        ac+=1
print(min(ac,n-bc)+min(bc,m-ac))


n, m = list(map(int, input().split()))
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
x = 0
y = 0
for c in a:
	if c % 2 == 0:
		x += 1
	else:
		y += 1
x1 = 0
y1 = 0
for c in b:
	if c % 2 == 0:
		x1 += 1
	else:
		y1 += 1
print(min(x, y1) +  min(y, x1))


n,m = list(map(int,input().split()))
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

oa = len([x for x in A if x%2])
ob = len([x for x in B if x%2])
ea = n - oa
eb = m - ob

print(min(oa,eb)+min(ob,ea))


from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import *
from itertools import *
import functools
import sys
from math import *
MAX = sys.maxsize
MAXN = 10**5+10
MOD = 10**9+7
def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def mhd(a,b,x,y):
    return abs(a-x)+abs(b-y)

def numIN(x = " "):
    return(list(map(int,sys.stdin.readline().strip().split(x))))

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN():
    return list(numIN())

def dis(x,y):
    a = y[0]-x[0]
    b = x[1]-y[1]
    return (a*a+b*b)**0.5

def lgcd(a):
    g = a[0]
    for i in range(1,len(a)):
        g = math.gcd(g,a[i])
    return g

def ms(a):
    msf = -MAX
    meh = 0
    st = en = be = 0
    for i in range(len(a)):
        meh+=a[i]
        if msf<meh:
            msf = meh
            st = be
            en = i
        if meh<0:
            meh = 0
            be = i+1
    return msf,st,en


def res(ans,t):
    print('Case #{}: {}'.format(t,ans))



n,m = numIN()
a = arrIN()
b = arrIN()
e1=e2=0
o1=o2=0

for i in a:
    if i%2:
        o1+=1
    else:
        e1+=1

for i in b:
    if i%2:
        o2+=1
    else:
        e2+=1


print(min(o1,e2)+min(e1,o2))




#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
 
##### Main ####
t=1
for tt in range(t):
    #n=int(input())
    n,m= map(int, sys.stdin.readline().split(' '))
    a=list(map(int,sys.stdin.readline().split(' ')))
    b=list(map(int,sys.stdin.readline().split(' ')))
    ae=0
    ao=0
    be=0
    bo=0
    for i in range(m):
        if(b[i]%2):
            bo+=1
        else:
            be+=1
    for i in range(n):
        if(a[i]%2):
            ao+=1
        else:
            ae+=1
    print(min(ao,be)+min(ae,bo)) 
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()

n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A = list(map(lambda x: x % 2, A))
B = list(map(lambda x: x % 2, B))
s = A.count(0)
t = A.count(1)
s2 = B.count(0)
t2 = B.count(1)
print(min(s, t2) + min(t, s2))

n, m = list(map(int, input().split()))
u = list(map(int, input().split()))
a = list(map(int, input().split()))
u1 = 0
u2 = 0
for i in range(n):
    if u[i] % 2 == 0:
        u1 += 1
    else:
        u2 += 1
a1 = 0
a2 = 0
for i in range(m):
    if a[i] % 2 == 0:
        a1 += 1
    else:
        a2 += 1
print(min(u1, a2) + min(u2, a1))


n, m = map(int, input().split())

a = [int(e)%2 for e in input().split()]
b = [int(e)%2 for e in input().split()]

a1 = sum(a)
a0 = n - a1
b1 = sum(b)
b0 = m - b1

print(min(a1, b0) + min(a0, b1))

[n, m] = [int(i) for i in input().split()]
a = [int(i) % 2 for i in input().split()]
b = [int(i) % 2 for i in input().split()]
print (min(sum(a), m - sum(b)) + min(sum(b), n - sum(a)))

import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
A=list(map(int,input().split()))
B=list(map(int,input().split()))

A0=[a for a in A if a%2==0]
A1=[a for a in A if a%2==1]
B0=[a for a in B if a%2==0]
B1=[a for a in B if a%2==1]

print(min(len(A0),len(B1))+min(len(A1),len(B0)))


n, m = list(map(int, input().split()))
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]
A, B, C, D = 0, 0, 0, 0
for i in a:
    if i % 2 == 0:
        A += 1
    else:
        B += 1
for i in b:
    if i % 2 == 0:
        C += 1
    else:
        D += 1
print(min(A, D) + min(B, C))


n,m = list(map(int,input().split()))
ai = list(map(int,input().split()))
bi = list(map(int,input().split()))
num = 0
num2 = 0
for i in range(n):
    num += int(ai[i] % 2)
for i in range(m):
    num2 += int(bi[i] % 2)
print(min(n - num,num2) + min(num, m - num2))


n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
odd1 = odd2 = even1 = even2 = 0
for i in a:
    if i%2: odd1+=1
    else: even1+=1
for i in b:
    if i%2: odd2+=1
    else: even2+=1
print(min(odd1, even2)+min(odd2, even1))


n, m = list(map(int, input().split()))
a = sum((int(ai) % 2 for ai in input().split()))
b = sum((int(bi) % 2 for bi in input().split()))
print(min(a, m - b) + min(b, n - a))


import sys

input = sys.stdin.readline

n, m = list(map(int, input().split()))

a = list(map(int, input().split()))
b = list(map(int, input().split()))

oddA = 0
evenA = 0
for i in a:
    if i%2:
        oddA += 1
    else:
        evenA += 1

oddB = 0
evenB = 0
for i in b:
    if i%2:
        oddB += 1
    else:
        evenB += 1

print(min(oddA, evenB) + min(oddB, evenA))