CF1415E.New Game Plus!

Wabbit is playing a game with $n$ bosses numbered from $1$ to $n$. The bosses can be fought in any order. Each boss needs to be defeated exactly once. There is a parameter called boss bonus which is initially $0$.

When the $i$-th boss is defeated, the current boss bonus is added to Wabbit's score, and then the value of the boss bonus increases by the point increment $c_i$. Note that $c_i$ can be negative, which means that other bosses now give fewer points.

However, Wabbit has found a glitch in the game. At any point in time, he can reset the playthrough and start a New Game Plus playthrough. This will set the current boss bonus to $0$, while all defeated bosses remain defeated. The current score is also saved and does not reset to zero after this operation. This glitch can be used at most $k$ times. He can reset after defeating any number of bosses (including before or after defeating all of them), and he also can reset the game several times in a row without defeating any boss.

Help Wabbit determine the maximum score he can obtain if he has to defeat all $n$ bosses.

瓦比特正在玩一个包含 $n$ 个 Boss 的游戏，这些 Boss 编号为 $1$ 到 $n$。Boss 可以以任意顺序挑战，每个 Boss 恰好需要被击败一次。游戏中有一个称为“Boss 加成”的参数，初始值为 $0$。

当击败第 $i$ 个 Boss 时，当前的 Boss 加成值会加到瓦比特的得分中，随后 Boss 加成值增加 $c_i$（即点数增量）。注意：$c_i$ 可能为负数，这意味着后续 Boss 所提供的分数将减少。

然而，瓦比特在游戏中发现了一个漏洞：在任意时刻，他都可以重置当前流程，开启一次“新游戏+”（New Game Plus）流程。该操作会将当前 Boss 加成值重置为 $0$，但所有已被击败的 Boss 仍保持已击败状态。当前得分也会被保留，不会因该操作而归零。此漏洞最多可使用 $k$ 次。他可以在击败任意数量的 Boss 后（包括尚未击败任何 Boss 之前，或击败全部 Boss 之后）执行重置；此外，他也可以连续多次重置而不击败任何 Boss。

请帮助瓦比特计算：在必须击败全部 $n$ 个 Boss 的前提下，他所能获得的最高得分是多少？

The first line of input contains two spaced integers $n$ and $k$ ($1 \leq n \leq 5 \cdot 10^5$, $0 \leq k \leq 5 \cdot 10^5$), representing the number of bosses and the number of resets allowed.

The next line of input contains $n$ spaced integers $c_1,c_2,\ldots,c_n$ ($-10^6 \leq c_i \leq 10^6$), the point increments of the $n$ bosses.

输入的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 5 \cdot 10^5$，$0 \leq k \leq 5 \cdot 10^5$），分别表示 Boss 的数量以及允许的重置次数。

第二行输入包含 $n$ 个用空格分隔的整数 $c_1,c_2,\ldots,c_n$（$-10^6 \leq c_i \leq 10^6$），表示这 $n$ 个 Boss 所提供的分数增量。

Output a single integer, the maximum score Wabbit can obtain by defeating all $n$ bosses (this value may be negative).

输出一个整数，表示 Wabbit 击败全部 $n$ 个 Boss 后所能获得的最高得分（该值可能为负数）。

In the first test case, no resets are allowed. An optimal sequence of fights would be

• Fight the first boss $(+0)$. Boss bonus becomes equal to $1$.
• Fight the second boss $(+1)$. Boss bonus becomes equal to $2$.
• Fight the third boss $(+2)$. Boss bonus becomes equal to $3$.

Thus the answer for the first test case is $0+1+2=3$.

In the second test case, it can be shown that one possible optimal sequence of fights is

• Fight the fifth boss $(+0)$. Boss bonus becomes equal to $5$.
• Fight the first boss $(+5)$. Boss bonus becomes equal to $4$.
• Fight the second boss $(+4)$. Boss bonus becomes equal to $2$.
• Fight the third boss $(+2)$. Boss bonus becomes equal to $-1$.
• Reset. Boss bonus becomes equal to $0$.
• Fight the fourth boss $(+0)$. Boss bonus becomes equal to $-4$.

Hence the answer for the second test case is $0+5+4+2+0=11$.

在第一个测试用例中，不允许重置。一种最优的战斗序列为：

• 战斗第一位首领 $(+0)$。首领奖励变为 $1$。
• 战斗第二位首领 $(+1)$。首领奖励变为 $2$。
• 战斗第三位首领 $(+2)$。首领奖励变为 $3$。

因此，第一个测试用例的答案为 $0+1+2=3$。

在第二个测试用例中，可以证明一种可能的最优战斗序列为：

• 战斗第五位首领 $(+0)$。首领奖励变为 $5$。
• 战斗第一位首领 $(+5)$。首领奖励变为 $4$。
• 战斗第二位首领 $(+4)$。首领奖励变为 $2$。
• 战斗第三位首领 $(+2)$。首领奖励变为 $-1$。
• 重置。首领奖励变为 $0$。
• 战斗第四位首领 $(+0)$。首领奖励变为 $-4$。

因此，第二个测试用例的答案为 $0+5+4+2+0=11$。