/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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
- 1 行目には、商品の数を表す N 、クーポンを適用できる最大個数を表す K が、スペース区切りで与えられる。
- 2 行目には、各商品の価格を表す D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
出力
支払う合計金額の最小値を 1 行で出力せよ。
入力例 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
Score : 300 pts
Problem Statement
Takahashi is about to go shopping on an online shopping site.
The shopping site has N items, and each item i has a price of D_i yen. Takahashi plans to purchase all the items.
Takahashi has a special discount coupon. By using this coupon, he can reduce the price of selected items to 0 yen. However, there is a restriction that the coupon can be applied to at most K items.
Takahashi wants to use the coupon optimally to minimize the total amount he pays. Find the minimum total amount he needs to pay when using the coupon optimally.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq D_i \leq 10^9
- All inputs are integers
Input
N K D_1 D_2 \ldots D_N
- The first line contains N, representing the number of items, and K, representing the maximum number of items the coupon can be applied to, separated by a space.
- The second line contains D_1, D_2, \ldots, D_N, representing the price of each item, separated by spaces.
Output
Output the minimum total amount to pay in one line.
Sample Input 1
5 2 100 250 300 150 200
Sample Output 1
450
Sample Input 2
7 3 500 1200 800 300 950 1100 450
Sample Output 2
2050
Sample Input 3
10 4 1000000000 999999999 500000000 750000000 250000000 800000000 600000000 400000000 350000000 900000000
Sample Output 3
2850000000