← 返回题目列表

Codeforces · 1430/B

B. 桶

中文机器翻译题面 查看原题

你有 $$$n$$$ 桶排成一排,从左到右从一个编号。最初,第 $$$i$$$ 个桶包含 $$$a_i$$$ 升水。

您可以将水从一个桶倒到另一个桶中。在一次倒水过程中,您可以选择两个不同的桶$$$x$$$和$$$y$$$(第$$$x$$$桶不应该是空的),然后将任意可能数量的水从桶$$$x$$$倒入桶$$$y$$$(可能是所有水)。您可能会假设桶的容量是无限的,因此您可以在每个桶中倒入任意数量的水。

如果您最多可以倒 $$$k$$$ 次水,请计算桶中最大水量和最小水量之间的最大可能差异。

一些示例:

- 如果你有四个桶,每个桶装有 $$$5$$$ 升水,并且 $$$k = 1$$$,则你可以将第二个桶中的 $$$5$$$ 升倒入第四个桶中,因此桶中的水量为 $$$[5, 0, 5, 10]$$$,最大和最小之间的差值为 $$$10$$$;
- 如果所有桶都是空的,则无法进行任何操作,因此最大和最小金额之间的差值仍然是$$$0$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$) - 桶的数量和可以浇注的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个桶的初始水量。

保证测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果您最多可以倒 $$$k$$$ 次水,请打印桶中最大水量和最小水量之间的最大可能差异。

示例

输入 #1

2
4 1
5 5 5 5
3 2
0 0 0

输出 #1

10
0