分数: 300 分
问题陈述
高桥出差回来了。他购买了 N 目的地的纪念品,但由于他的行李箱最多只能容纳 N - K 物品,他必须放弃 K 纪念品。
每个 N 纪念品编号为 1 to N和纪念品 i (1 \leq i \leq N) 具有满意度值 D_i。满意度值代表将纪念品带回家所获得的幸福感。
高桥会选择 K 独特的纪念品 N 纪念品放弃,剩下的全部带回家 N - K 纪念品。他想最优地选择放弃哪些纪念品,从而最大化他带回家的纪念品的总满意度。
求他带回家的纪念品的最大可能总满意度值。
约束
- 1 \leq K < N \leq 2 \times 10^5
- 1 \leq D_i \leq 10^9
- 所有输入均为整数
输入
N K D_1 D_2 \ldots D_N
- 第一行包含两个用空格分隔的整数: N,纪念品总数,以及 K,放弃的纪念品数量。
- 第二行包含整数 D_i (1 \leq i \leq N),代表纪念品的满意度值 i,按顺序给出 D_1, D_2, \ldots, D_N,用空格分隔。
输出
在一行上打印他带回家的纪念品的最大可能总满意度值。
示例输入 1
5 2 3 1 4 1 5
示例输出 1
12
示例输入 2
8 3 10 20 30 40 50 60 70 80
示例输出 2
300
示例输入 3
15 6 1000000000 1 999999999 2 888888888 3 777777777 4 666666666 5 555555555 6 444444444 7 333333333
示例输出 3
5666666669