B - お土産の選別 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は旅行から帰ってきました。旅行先で N 個のお土産を購入しましたが、スーツケースには最大 N - K 個しか入らないため、K 個のお土産を諦めなければなりません。

N 個のお土産にはそれぞれ 1 から N までの番号が付いており、お土産 i（1 \leq i \leq N）には満足度 D_i が設定されています。満足度は、そのお土産を持ち帰ったときに得られる嬉しさを表します。

高橋君は、N 個のお土産の中から異なる K 個を選んで諦め、残りの 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
  • 1 行目には、お土産の総数を表す整数 N と、諦めるお土産の個数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、お土産 i の満足度を表す整数 D_i（1 \leq i \leq N）が、D_1, D_2, \ldots, D_N の順にスペース区切りで与えられる。

出力

持ち帰るお土産の満足度の合計値の最大値を 1 行で出力してください。

入力例 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

Score : 300 pts

Problem Statement

Takahashi has returned from a trip. He purchased N souvenirs at his destination, but since his suitcase can hold at most N - K items, he must give up K souvenirs.

Each of the N souvenirs is numbered from 1 to N, and souvenir i (1 \leq i \leq N) has a satisfaction value D_i. The satisfaction value represents the happiness gained from bringing that souvenir home.

Takahashi will choose K distinct souvenirs from the N souvenirs to give up, and bring home all of the remaining N - K souvenirs. He wants to optimally choose which souvenirs to give up so as to maximize the total satisfaction value of the souvenirs he brings home.

Find the maximum possible total satisfaction value of the souvenirs he brings home.

Constraints

  • 1 \leq K < N \leq 2 \times 10^5
  • 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 two integers separated by a space: N, the total number of souvenirs, and K, the number of souvenirs to give up.
  • The second line contains the integers D_i (1 \leq i \leq N), representing the satisfaction value of souvenir i, given in the order D_1, D_2, \ldots, D_N, separated by spaces.

Output

Print the maximum possible total satisfaction value of the souvenirs he brings home, on a single line.

Sample Input 1

5 2
3 1 4 1 5

Sample Output 1

12

Sample Input 2

8 3
10 20 30 40 50 60 70 80

Sample Output 2

300

Sample Input 3

15 6
1000000000 1 999999999 2 888888888 3 777777777 4 666666666 5 555555555 6 444444444 7 333333333

Sample Output 3

5666666669