Drinks Choosing
Contest: Codeforces Round 574 (Div. 2)
Difficulty rating: 1000
Tags: greedy, math

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 format:
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 format:
Print exactly one integer — the maximum number of students that can get a favorite drink.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
5 3
1
3
1
1
2

Example output:
4

Example input:
10 3
2
1
3
2
3
3
1
3
1
2

Example output:
9

Editorial:
Let's take a look on a students. If two students have the same favorite drink, let's take one set with this drink. Let the number of such students (which we can satisfy as pairs) be $$$good$$$. Because the number of sets is $$$\lceil\frac{n}{2}\rceil$$$ we always can do it. So there are students which are the only with their favorite drinks remain. It is obvious that if we take one set we can satisfy at most one student (and one of the others will gain not his favorite drink). Let the number of such students (which remain after satisfying pairs of students) be $$$bad$$$. Then the answer is $$$good + \lceil\frac{bad}{2}\rceil$$$.