分数: 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