← 返回题目列表

AtCoder · keyence2021_b

B. 墨西哥盒

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

分数: 400 点

问题陈述

Snuke 有 N 球,每个球上都写有一个整数。 球上的数字是 a_1, a_2, \ldots, a_N.

他决定把这些 N 球入 K 盒。每个球都必须在某个盒子里,但也可能有零个或多个球的盒子。

当他把球放入盒子后,每个盒子的盖子上都会显示一个整数。 让 x 是方框上显示的整数。 x 是最小值 非负 整数,使得盒子不包含球 x。 例如,空盒子的盖子会显示 0;有球的盒子的盖子 0, 1, 3, 5 将显示 2;有球的盒子的盖子 1, 2, 3 将显示 0.

求盖子显示的整数的最大可能总和。

约束

  • 输入中的所有值都是整数。
  • 1 \leq K \leq N \leq 3 \times 10^{5}
  • 0 \leq a_i < N

输入

输入由标准输入按以下格式给出:

N K
a_1 a_2 \cdots a_N

输出

打印盖子显示的整数的最大可能总和。


示例输入 1

4 2
0 1 0 2

示例输出 1

4
  • 最佳解决方案是分配球组 \{0,1,2 \},\{0\} 到盒子里。
  • 在这种情况下,盖子显示 3, 1分别为总共 4.

示例输入 2

5 2
0 1 1 2 3

示例输出 2

4
  • 最佳解决方案是分配(多)组球 \{0,1,1,2,3\}, \{\} 到盒子里。
  • 在这种情况下,盖子显示 4, 0分别为总共 4.
  • 请注意,我们可能有空盒子。

示例输入 3

20 4
6 2 6 8 4 5 5 8 4 1 7 8 0 3 6 1 1 8 3 0

示例输出 3

11