/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は、あるオンラインショッピングサイトで開催されている「ポイント獲得キャンペーン」に参加することになりました。
このキャンペーンでは、N 個の商品が用意されており、各商品 i（1 \leq i \leq N）を購入するとポイント P_i を獲得できます。
高橋君はこれらの商品の中から好きな商品を選んで購入することができますが、同じ商品を複数回購入することはできず、購入できる商品の個数は最大 K 個までです。K \geq N の場合はすべての商品を購入することもでき、また、1 つも購入しないことも許されます。
高橋君が獲得できる合計ポイントの最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 2 \times 10^5
- 1 \leq P_i \leq 10^9
- 入力はすべて整数
入力
N K P_1 P_2 \ldots P_N
- 1 行目には、商品の個数を表す整数 N と、購入できる商品の最大個数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各商品で獲得できるポイントを表す整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。P_i は商品 i を購入したときに獲得できるポイントを表す。
出力
高橋君が獲得できる合計ポイントの最大値を整数として 1 行で出力せよ。
入力例 1
5 3 10 30 20 50 40
出力例 1
120
入力例 2
4 6 100 200 300 400
出力例 2
1000
入力例 3
10 5 1000000000 999999999 1 500000000 750000000 250000000 800000000 600000000 900000000 100000000
出力例 3
4449999999
Score : 300 pts
Problem Statement
Takahashi is going to participate in a "Point Earning Campaign" held on an online shopping site.
In this campaign, N products are available, and purchasing product i (1 \leq i \leq N) earns P_i points.
Takahashi can choose and purchase any products he likes from among these products, but he cannot purchase the same product more than once, and he can purchase at most K products. If K \geq N, he may purchase all products, and it is also allowed to purchase none at all.
Find the maximum total points Takahashi can earn.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 2 \times 10^5
- 1 \leq P_i \leq 10^9
- All inputs are integers
Input
N K P_1 P_2 \ldots P_N
- The first line contains an integer N representing the number of products and an integer K representing the maximum number of products that can be purchased, separated by a space.
- The second line contains integers P_1, P_2, \ldots, P_N representing the points earned from each product, separated by spaces. P_i represents the points earned when purchasing product i.
Output
Output the maximum total points Takahashi can earn as an integer on a single line.
Sample Input 1
5 3 10 30 20 50 40
Sample Output 1
120
Sample Input 2
4 6 100 200 300 400
Sample Output 2
1000
Sample Input 3
10 5 1000000000 999999999 1 500000000 750000000 250000000 800000000 600000000 900000000 100000000
Sample Output 3
4449999999