暑期信息学学校的老朋友还记得以前的训练营,每个学生都会在 vechorka(晚餐)上选择一杯自己选择的饮料。或者故事可能更复杂?
一栋楼里住着 $$$n$$$ 名学生,并且他们每个人最喜欢的饮料 $$$a_i$$$ 都是已知的。所以你知道 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$,其中 $$$a_i$$$ ($$$1 \le a_i \le k$$$) 是第 $$$i$$$ 学生最喜欢的饮料类型。饮料类型的编号从 $$$1$$$ 到 $$$k$$$。
饮料套装数量无限。每套均由同一饮料的两份组成。换句话说,有$$$k$$$种饮料套装,第$$$j$$$种包含两份饮料$$$j$$$。每种 $$$k$$$ 类型的可用组数是无限的。
您知道学生将收到尽可能少的组数,以便为所有学生提供一杯饮料。显然,集合的数量将恰好为 $$$\lceil \frac{n}{2} \rceil$$$,其中 $$$\lceil x \rceil$$$ 是 $$$x$$$ 向上舍入。
学生收到套装后,将根据自己的选择分配自己的份量:每个学生将获得一份。请注意,如果 $$$n$$$ 为奇数,则一部分将保持未使用,学生的老师将喝掉它。
如果 $$$\lceil \frac{n}{2} \rceil$$$ 套装被最佳选择并且学生之间最佳分配部分,那么最多有多少学生可以获得他们最喜欢的饮料?
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 1\,000$$$) — 大楼内的学生人数和不同饮料的数量。
接下来的 $$$n$$$ 行包含学生最喜欢的饮料。第 $$$i$$$ 行包含从 $$$1$$$ 到 $$$k$$$ 的单个整数 — 第 $$$i$$$ 学生最喜欢的饮料类型。
输出
打印一个整数——可以获得最喜欢的饮料的学生的最大数量。
示例
输入 #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
注意
在第一个示例中,学生可以选择三套饮料 $$$1$$$、$$$1$$$ 和 $$$2$$$(因此他们将有两套,每套两杯 $$$1$$$ 类型的饮料,一套有两杯 $$$2$$$ 类型的饮料,因此份量将为 $$$1, 1, 1, 1, 2, 2$$$)。这样,除了第二个学生之外,所有学生都会得到他们最喜欢的饮料。
另一个可能的答案是包含饮料 $$$1$$$、$$$2$$$ 和 $$$3$$$ 的套餐。在这种情况下,这些部分将为 $$$1, 1, 2, 2, 3, 3$$$。然后,除一名学生外,所有学生都将获得他们最喜欢的饮料。唯一不会获得最喜欢饮料的学生是 $$$a_i = 1$$$(即第一、第三或第四)的学生。