Drinks Choosing

题意翻译

给出 $n$ 个元素，一共有 $k$ 个不同元素，请你给出 $\lceil \frac{n}{2} \rceil$ 个二元组，每个二元组中的两个元素相同，使你给出的所有元素中与原元素相同个数最多。 请你给出最多的相同个数。

题目描述

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.

输入输出样例

输入样例 #1

5 3
1
3
1
1
2

输出样例 #1

4

输入样例 #2

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

输出样例 #2

9

说明

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