Wabbit 正在与 $$$n$$$ 老板玩游戏,老板编号从 $$$1$$$ 到 $$$n$$$。 Boss 可以按任意顺序进行战斗。每个 Boss 都需要被击败一次。有一个参数叫做老板奖金,最初是$$$0$$$。
当第$$$i$$$个boss被击败时,当前boss奖励会添加到Wabbit的分数中,然后boss奖励的值会增加点增量$$$c_i$$$。请注意,$$$c_i$$$ 可以为负数,这意味着其他老板现在给出的分数更少。
然而,Wabbit 在游戏中发现了一个故障。在任何时间点,他都可以重置游戏流程并开始“新游戏+”游戏流程。这会将当前的 Boss 奖励设置为 $$$0$$$,而所有被击败的 Boss 仍然被击败。当前分数也会被保存,并且在此操作后不会重置为零。此故障最多可使用 $$$k$$$ 次。他可以在击败任意数量的 Boss 后(包括击败所有 Boss 之前或之后)重置游戏,也可以在不击败任何 Boss 的情况下连续多次重置游戏。
帮助 Wabbit 确定如果他必须击败所有 $$$n$$$ 头目,他可以获得的最高分数。
输入
输入的第一行包含两个空格整数$$$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$$$ 老板的点增量。
输出
输出单个整数,Wabbit击败所有$$$n$$$个boss可以获得的最大分数(该值可能为负数)。
示例
输入 #1
3 0 1 1 1
输出 #1
3
输入 #2
5 1 -1 -2 -3 -4 5
输出 #2
11
输入 #3
13 2 3 1 4 1 5 -9 -2 -6 -5 -3 -5 -8 -9
输出 #3
71
注意
在第一个测试用例中,不允许重置。最佳的战斗顺序是
- 与第一个boss战斗$$$(+0)$$$。老板奖金等于 $$$1$$$。
- 与第二个 boss $$$(+1)$$$ 战斗。老板奖金等于 $$$2$$$。
- 与第三个 boss $$$(+2)$$$ 战斗。老板奖金等于 $$$3$$$。
因此第一个测试用例的答案是 $$$0+1+2=3$$$。
在第二个测试用例中,可以证明一种可能的最佳战斗序列是
- 与第五个 boss $$$(+0)$$$ 战斗。老板奖金等于 $$$5$$$。
- 与第一个 Boss $$$(+5)$$$ 战斗。老板奖金等于 $$$4$$$。
- 与第二个 boss $$$(+4)$$$ 战斗。老板奖金等于 $$$2$$$。
- 与第三个 boss $$$(+2)$$$ 战斗。老板奖金变为$$$-1$$$。
- 重置。老板奖金变为$$$0$$$。
- 与第四个 boss $$$(+0)$$$ 战斗。老板奖金变为$$$-4$$$。
因此第二个测试用例的答案是$$$0+5+4+2+0=11$$$。