你有 $$$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