← 返回题目列表

AtCoder · awc0038_b

B. 纪念品选择

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

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