← 返回题目列表

AtCoder · awc0001_c

C. 折扣券

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

分数: 300 分

问题陈述

高桥准备去网上购物网站购物。

购物网站有 N 项目,以及每个项目 i 的价格为 D_i 日元。高桥计划购买所有物品。

高桥有特别折扣券。通过使用这张优惠券,他可以将所选商品的价格降低至 0 日元。但优惠券的使用次数有限制 K 项目。

高桥希望以最佳方式使用优惠券,以尽量减少他支付的总金额。求出他在最佳使用优惠券时需要支付的最低总金额。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq N
  • 1 \leq D_i \leq 10^9
  • 所有输入均为整数

输入

N K
D_1 D_2 \ldots D_N
  • 第一行包含 N,代表项目数量,以及 K,代表该优惠券可以应用的最大商品数,以空格分隔。
  • 第二行包含 D_1, D_2, \ldots, D_N,代表每件商品的价格,以空格分隔。

输出

一行输出最小支付总额。


示例输入 1

5 2
100 250 300 150 200

示例输出 1

450

示例输入 2

7 3
500 1200 800 300 950 1100 450

示例输出 2

2050

示例输入 3

10 4
1000000000 999999999 500000000 750000000 250000000 800000000 600000000 400000000 350000000 900000000

示例输出 3

2850000000