Old timers of Summer Informatics School can remember previous camps in which each student was given a drink of his choice on the vechorka (late-evening meal). Or may be the story was more complicated?

There are $n$ students living in a building, and for each of them the favorite drink $a_i$ is known. So you know $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ ($1 \le a_i \le k$) is the type of the favorite drink of the $i$-th student. The drink types are numbered from $1$ to $k$.

There are infinite number of drink sets. Each set consists of exactly two portions of the same drink. In other words, there are $k$ types of drink sets, the $j$-th type contains two portions of the drink $j$. The available number of sets of each of the $k$ types is infinite.

You know that students will receive the minimum possible number of sets to give all students exactly one drink. Obviously, the number of sets will be exactly $\lceil \frac{n}{2} \rceil$, where $\lceil x \rceil$ is $x$ rounded up.

After students receive the sets, they will distribute their portions by their choice: each student will get exactly one portion. Note, that if $n$ is odd then one portion will remain unused and the students' teacher will drink it.

What is the maximum number of students that can get their favorite drink if $\lceil \frac{n}{2} \rceil$ sets will be chosen optimally and students will distribute portions between themselves optimally?


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 1\,000$) — the number of students in the building and the number of different drinks.

The next $n$ lines contain student's favorite drinks. The $i$-th line contains a single integer from $1$ to $k$ — the type of the favorite drink of the $i$-th student.


-----Output-----

Print exactly one integer — the maximum number of students that can get a favorite drink.


-----Examples-----
Input
5 3
1
3
1
1
2

Output
4

Input
10 3
2
1
3
2
3
3
1
3
1
2

Output
9



-----Note-----

In the first example, students could choose three sets with drinks $1$, $1$ and $2$ (so they will have two sets with two drinks of the type $1$ each and one set with two drinks of the type $2$, so portions will be $1, 1, 1, 1, 2, 2$). This way all students except the second one will get their favorite drinks.

Another possible answer is sets with drinks $1$, $2$ and $3$. In this case the portions will be $1, 1, 2, 2, 3, 3$. Then all the students except one will gain their favorite drinks. The only student that will not gain the favorite drink will be a student with $a_i = 1$ (i.e. the first, the third or the fourth).

Difficulty: interview

Starter code:

Solutions:
def main():
    import sys
    input = sys.stdin.readline
    
    n, k = map(int, input().split())
    
    cnt = [0] * k
    for i in range(n):
        cnt[int(input()) - 1] += 1
    
    dead = 0
    ans = 0
    
    for i in cnt:
        if i & 1:
            dead += 1
            ans += i - 1
        else:
            ans += i
    
    if n & 1:
        print(ans + (dead + 1) // 2)
    else:
        print(ans + dead // 2)
    
    return 0

main()

n,k=map(int,input().split())
l1=[0]*k
for i in range(n):
    x=int(input())
    l1[x-1]+=1
ans=0
odds=0
for item in l1:
    if item%2==0:
        ans+=item
    else :
        ans+=(item-1)
        odds+=1
if n%2==0:
    print(ans+odds//2)
else :
    print(ans+(odds-1)//2+1)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from collections import Counter


n, k  = getList()


stu = []
for i in range(n):
    d = getN()
    stu.append(d)

cnt = Counter(stu)
# print(cnt)
ans = 0
for v in cnt.values():
    ans += (v // 2) * 2

ans += (n - ans + 1) // 2

print(ans)

import sys

n, k = list(map(int, sys.stdin.readline().strip().split()))
A = [0] * (k+1)
for i in range (0, n):
    a = int(sys.stdin.readline().strip())
    A[a] = A[a] + 1
x = 0
y = 0
for i in range (1, k + 1):
    x = x + A[i] // 2
    y = y + A[i] % 2
print(2 * x + (y+1) // 2)

n, k = [int(i) for i in input().split()]
s = [0]*k
for i in range(n):
    s[int(input())-1]+=1
p = 0
for i in s:
    p+=(i%2)
print(n-p//2)

n,k = map(int,input().split())
from collections import defaultdict
k = (n+1)//2
full = 0
odd = 0
count = defaultdict(int)
for x in range(n):
    x = int(input())
    count[x]+=1
for key,v in count.items():
    full += v//2
    odd += v%2

total = 0
step = min(k,full)

k-=step
total+=step*2
step = min(odd,k)

total+=step
print (total) 

a, b = list(map(int,input().split()))
n = [0] * b
for i in range(a):
    k = int(input())
    n[k - 1] += 1
cnt = 0
for x in n:
    cnt += x % 2
print(a - cnt // 2)

n,k = list(map(int,input().split()))
favdrs = [0] * (k+1)
for i in range(n):
    temp = int(input())
    favdrs[temp] += 1
num = 0
for i in range(k+1):
    if favdrs[i] % 2 == 1:
        num += 1
print(n - num // 2)


n, k = [int(i) for i in input().split()]
dic = [0] * (k+1) 
for j in range(n):
    a = int(input())
    dic[a] += 1
sets = 0
for d in dic:
    sets += d//2

tot = (n+1)//2
print(sets + tot )


n, k = list(map(int, input().split()))
cnt = [0] * k
for i in range(n):
    x = int(input())
    cnt[x - 1] += 1
ans = 0
p = 0
for i in range(k):
    p += cnt[i] // 2
    ans += cnt[i] // 2 * 2
ans += (n + 1) // 2 - p
print(ans)


from collections import defaultdict

n, k = [int(i) for i in input().split()]

x = []
v = defaultdict(int)
for i in range(n):
    v[int(input())] += 1
a = 0

for i in v.values():
    a += i // 2

print(2 * a + (((n+1)//2)-a))

from math import ceil
n, k = map(int, input().split())
drinks = [False for i in range(k + 1)]
satisfied = 0
for i in range(n):
    d = int(input())
    if drinks[d]:
        satisfied += 2
    drinks[d] = not drinks[d]
unsat = len(list(filter(lambda x: x, drinks)))
print(satisfied + ceil(unsat / 2))

n,k=list(map(int,input().split()))
d=[0]*(k+1)
for i in range(n):
    d[(int(input()))]+=1
r=0
ans=0
for i in d:
    ans+=(i//2)*2
    r+=i%2
print(ans+-(-r//2))


n, k = list(map(int, input().split()))
a = []
for _ in range(n):
	z = int(input())
	a.append(z)
if n % 2:
	a.append(0)
a.sort()
i = 0
res = 0
ost = 0
while i < len(a) - 1:
	if a[i] == a[i + 1]:
		i += 2
		res += 2
	else:
		i += 1
		ost += 1
if ost % 2:
	print(res + (ost + 1) // 2)
else:
	print(res + ost // 2)


n, k = map(int, input().split())
d = [0]*(k+1)
for i in range(n):
    a = int(input())
    d[a] += 1
d.sort(reverse=True)
count = 0
for i in range(k):
    count += d[i] - d[i]%2
    d[i] = d[i]%2
d.append(1)
count += d.count(1)//2
print(count)

from math import ceil
n, k = list(map(int, input().split()))
a = []
for i in range(n):
  a.append(int(input()))
res = 0
d = [0] * 1024
for i in a:
  d[i] += 1
for i in d:
  res += 2 * (i // 2)
res = res + ceil((n - res) / 2)
print(res)


''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import cProfile, math
from collections import Counter,defaultdict,deque
from bisect import bisect_left,bisect,bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size
fac_warmup = False
printHeap = str()
memory_constrained = False
P = 10**9+7
import sys

class merge_find:
    def __init__(self,n):
        self.parent = list(range(n))
        self.size = [1]*n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]
    def find(self,a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]
    def merge(self,a,b):
        a = self.find(a)
        b = self.find(b)
        if a==b:
            return
        if self.size[a]<self.size[b]:
            a,b = b,a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]
    def set_size(self, a):
        return self.size[self.find(a)]
    def __len__(self):
        return self.num_sets

def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")

def primeFactors(n): #n**0.5 complex 
    factors = dict()
    for i in range(2,math.ceil(math.sqrt(n))+1):  
        while n % i== 0: 
            if i in factors:
                factors[i]+=1
            else: factors[i]=1
            n = n // i 
    if n>2:
        factors[n]=1
    return (factors)

def all_factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def fibonacci_modP(n,MOD):
    if n<2: return 1
    #print (n,MOD)
    return (cached_fn(fibonacci_modP, (n+1)//2, MOD)*cached_fn(fibonacci_modP, n//2, MOD) + cached_fn(fibonacci_modP, (n-1) // 2, MOD)*cached_fn(fibonacci_modP, (n-2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n , p): 
    if (p <= n): 
        return 0
    res = (p - 1) 
    for i in range (n + 1, p): 
        res = (res * cached_fn(InverseEuler,i, p)) % p 
    return res 

def binary(n,digits = 20):
    b = bin(n)[2:]
    b = '0'*(digits-len(b))+b
    return b

def isprime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True

def generate_primes(n):
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * 2, n+1, p): 
                prime[i] = False
        p += 1
    return prime

factorial_modP = []
def warm_up_fac(MOD):
    nonlocal factorial_modP,fac_warmup
    if fac_warmup: return
    factorial_modP= [1 for _ in range(fac_warmup_size+1)]
    for i in range(2,fac_warmup_size):
        factorial_modP[i]= (factorial_modP[i-1]*i) % MOD
    fac_warmup = True

def InverseEuler(n,MOD):
    return pow(n,MOD-2,MOD)

def nCr(n, r, MOD):
    nonlocal fac_warmup,factorial_modP
    if not fac_warmup:
        warm_up_fac(MOD)
        fac_warmup = True
    return (factorial_modP[n]*((pow(factorial_modP[r], MOD-2, MOD) * pow(factorial_modP[n-r], MOD-2, MOD)) % MOD)) % MOD

def test_print(*args):
    if testingMode:
        print(args)

def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")

def display_2D_list(li):
    for i in li:
        print(i)
def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm+=i
        res.append(sm)
    return res

def get_int():
    return int(stdin.readline().strip())

def get_tuple():
    return map(int, stdin.readline().split())

def get_list():
    return list(map(int, stdin.readline().split()))
import heapq,itertools
pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>' 
def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heapq.heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heapq.heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')
memory = dict()
def clear_cache():
    nonlocal memory
    memory = dict()
def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result

def ncr (n,r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))
def binary_serach(i,li):
    #print("Search for ",i)
    fn = lambda x: li[x]-x//i
    x = -1
    b = len(li)
    while b>=1:
        #print(b,x)
        while b+x<len(li) and fn(b+x)>0: #Change this condition 2 to whatever you like
            x+=b
        b=b//2
    return x

# -------------------------------------------------------------- MAIN PROGRAM
TestCases = False
testingMode = False
fac_warmup_size = 10**5+100
optimiseForReccursion = False #Can not be used clubbed with TestCases # WHen using recursive functions, use Python 3
from math import factorial

def main():
    n, k = get_tuple()
    li = []
    paired = 0
    for i in range(n):
        x = get_int()
        if x in li:
            paired+=2
            li.remove(x)
        else:
            li.append(x)
    print(paired+(len(li)+1)//2)
    
# --------------------------------------------------------------------- END=


if TestCases: 
    for i in range(get_int()): 
        cProfile.run('main()') if testingMode else main() 
else: (cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()

n,k=list(map(int,input().split()))
arr = [0]*k
for i in range(n):
    arr[int(input())-1]+=1
shaman=1
ans = 0
for i in range(k):
    ans += (arr[i]//2)*2
    shaman += arr[i]%2
print(ans + (shaman//2))





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

a = []
s = set()
ans = 0
k = 0
for i in range(n):
    a = int(input())
    if a in s:
        s.remove(a)
        ans += 2
        k += 1
    else:
        s.add(a)
print(ans + (n // 2 + n % 2) - k)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time

(n, k) = (int(i) for i in input().split())

start = time.time()

b = [ 0 for i in range(k)]

for i in range(n):
    now = int(input())-1
    b[now] += 1

ost = 0
ans = 0

for i in range(k):
    d = b[i] % 2
    ans += b[i] - d
    ost += d

ans += ost//2 + ost%2
print(ans)

finish = time.time()
#print(finish - start)


n,k=list(map(int,input().split()))
dict1={}
for i in range(n):
	x=int(input())
	try:
		dict1[x]+=1
	except:
		KeyError
		dict1[x]=1
ans=0
flagcount=0
for i in list(dict1.keys()):
	ans+=((dict1[i])//2)*2
	if(dict1[i]%2!=0):
		flagcount+=1
if(n%2==0):
	ans+=(flagcount)//2
else:
	ans+=(flagcount)//2
	ans+=1
print(ans)



from math import ceil

n,k = list(map(int,input().split()))
a = [0]*k
for i in range(n):
    q = int(input())
    a[q-1] += 1
j = 0
ans = 0
for i in a:
    j += i//2
    ans += i%2

print(n-(ans-(ceil(n/2)-j)))

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

u = 0
arr = [0]*k

for i in range(n):
    a = int(input())
    arr[a-1] += 1

for i in range(k):
    u += arr[i]//2

print((n+1)//2 + u)

n, k = list(map(int, input().split()))
l = [0] * (k + 1)
for i in range(n):
    a = int(input())
    l[a] += 1
ans = 0
cnt = 0
for i in range(k + 1):
    ans += l[i]
    if (l[i] % 2 == 1):
        cnt += 1
        ans -= 1
print(ans + cnt // 2 + cnt % 2)