有\(n\)個物品，每個物品有一個價值\(v_i\)，我們可以從中選出最多\(k\)個物品使其價值總和最大。
\(1 \le k \le n \le 10^5,0 \le v_i \le 10^9\)

對於這個問題我們可以令\(dp[i][j]\)為從前\(i\)種物品選其中\(j\)種的答案
那我們可以得出轉移式\(dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+vi)\)
但這樣時間複雜度是\(O(n*k)\)，對這題的限制顯然過不了
所以換個想法，考慮另一個問題：
有\(n\)個物品，沒有拿取次數限制，但每取一個物品會收價值\(p\)的手續費
那這個問題可以列出時間複雜度\(O(n)\)的轉移式：\(f[i]\) 為考慮前\(i\)個物品的答案
則\(f[i] = max(f[i-1], f[i-1]+vi-p)\)
假設當我們每次收的手續費是\(p\)的時候發生最大值時選了\(k\)個物品，那因為\(f\)和\(dp\)只差在取物時有沒有收取手續費\(p\)
因此我們可以知道\(f[n] = dp[n][k] - kp\)
另外當這個問題的手續費\(p\)越大時，要得到最大值可以選的物品數量就越小，有單調性
因此我們可以二分搜這個\(p\)再把搜到的答案加回\(k*p\)就可以得到我們原題想要的答案

輸入說明

第一行有兩個數字 \(n, k (1 \le k \le n \le 10^5)\)
第二行有\(n\)個數字 \(0 \le v_i \le 10^9\)

輸出說明

輸出一選最多\(k\)個物品的價值總和最大值

範例輸入1

6 4
1 1 4 5 1 4

範例輸出1

14

最佳選法不唯一，對於這個側資選最後四個可以獲得最價值

子題配分