A. Drinks Choosing
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?
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.
Print exactly one integer — the maximum number of students that can get a favorite drink.
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).