JebTrains的员工正在路上庆祝今年的第256天! JebTrains 有 $$$n$$$ 员工和 $$$k$$$ 团队。每个员工都是某个(恰好是一个)团队的成员。所有团队的编号从 $$$1$$$ 到 $$$k$$$。您将获得一个数字数组 $$$t_1, t_2, \dots, t_n$$$,其中 $$$t_i$$$ 是第 $$$i$$$ 员工的团队编号。
JebTrains 将租一辆巴士接送员工参加盛宴。巴士将乘坐一趟或多趟。一辆巴士可以搭载整个团队或两个整个团队。如果三个或更多团队一起骑行,他们可能会开始一个新项目,这被认为是不可接受的。禁止拆分团队,因此团队的所有成员都应乘坐同一趟车。
可以租用任何容量的巴士$$$s$$$。这样的巴士单次可搭载 $$$s$$$ 人。租金总成本等于 $$$s \cdot r$$$ burles,其中 $$$r$$$ 是乘车次数。请注意,不可能租用两辆或更多巴士。
帮助 JebTrains 计算满足上述所有条件、让所有员工参加盛宴所需的最低租金成本。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 5\cdot10^5, 1 \le k \le 8000$$$) — JebTrains 中的员工数量和团队数量。第二行包含整数序列 $$$t_1, t_2, \dots, t_n$$$,其中 $$$t_i$$$ ($$$1 \le t_i \le k$$$) 是第 $$$i$$$ 员工的团队编号。每个团队至少包含一名员工。
输出
打印最低租金。
示例
输入 #1
6 3 3 1 2 3 2 3
输出 #1
6
输入 #2
10 1 1 1 1 1 1 1 1 1 1 1
输出 #2
10
输入 #3
12 4 1 2 3 1 2 3 4 1 2 1 2 1
输出 #3
12