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