CF1415E New Game Plus!

Wabbit 正在和 $ n $ 个编号为 $ 1 $ 到 $ n $ 的 Boss 玩游戏。这些 Boss 可以以任意顺序挑战，每个 Boss 需要被击败恰好一次。有一个名为 Boss 奖励的参数，初始值为 $ 0 $。 当第 $ i $ 个 Boss 被击败时，当前的 Boss 奖励会被加到 Wabbit 的得分上，然后 Boss 奖励的值增加 $ c_i $。注意，$ c_i $ 可能为负数，这意味着之后的 Boss 能获得的分数会减少。 然而，Wabbit 发现了游戏中的一个漏洞。在任何时刻，他都可以重置游戏并开始一次“新游戏+”流程。这会将当前的 Boss 奖励重置为 $ 0 $，而所有已击败的 Boss 依然保持已击败状态。当前得分也会被保留，不会因重置而归零。这个漏洞最多可以使用 $ k $ 次。他可以在击败任意数量的 Boss 后重置（包括在击败所有 Boss 之前或之后），也可以连续多次重置而不击败任何 Boss。 请你帮助 Wabbit 计算，如果他必须击败所有 $ n $ 个 Boss，他最多能获得多少分数（这个值可能为负数）。

输入的第一行包含两个用空格分隔的整数 $ 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 $），表示每个 Boss 的分数增量。

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

在第一个测试样例中，不允许重置。最优的挑战顺序如下： - 挑战第一个 Boss（得分 $ +0 $）。Boss 奖励变为 $ 1 $。 - 挑战第二个 Boss（得分 $ +1 $）。Boss 奖励变为 $ 2 $。 - 挑战第三个 Boss（得分 $ +2 $）。Boss 奖励变为 $ 3 $。 因此答案为 $ 0+1+2=3 $。 在第二个测试样例中，可以证明一种可能的最优挑战顺序如下： - 挑战第五个 Boss（得分 $ +0 $）。Boss 奖励变为 $ 5 $。 - 挑战第一个 Boss（得分 $ +5 $）。Boss 奖励变为 $ 4 $。 - 挑战第二个 Boss（得分 $ +4 $）。Boss 奖励变为 $ 2 $。 - 挑战第三个 Boss（得分 $ +2 $）。Boss 奖励变为 $ -1 $。 - 重置。Boss 奖励变为 $ 0 $。 - 挑战第四个 Boss（得分 $ +0 $）。Boss 奖励变为 $ -4 $。 因此答案为 $ 0+5+4+2+0=11 $。 由 ChatGPT 4.1 翻译