← 返回题目列表

Codeforces · 1250/B

B. 盛宴和巴士

中文机器翻译题面 查看原题

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