CF1430B.Barrels

You have $n$ barrels lined up in a row, numbered from left to right from one. Initially, the $i$-th barrel contains $a_i$ liters of water.

You can pour water from one barrel to another. In one act of pouring, you can choose two different barrels $x$ and $y$ (the $x$-th barrel shouldn't be empty) and pour any possible amount of water from barrel $x$ to barrel $y$ (possibly, all water). You may assume that barrels have infinite capacity, so you can pour any amount of water in each of them.

Calculate the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most $k$ times.

Some examples:

• if you have four barrels, each containing $5$ liters of water, and $k = 1$, you may pour $5$ liters from the second barrel into the fourth, so the amounts of water in the barrels are $[5, 0, 5, 10]$, and the difference between the maximum and the minimum is $10$;
• if all barrels are empty, you can't make any operation, so the difference between the maximum and the minimum amount is still $0$.

你有 $n$ 个桶排成一排，从左到右依次编号为 $1$ 到 $n$。初始时，第 $i$ 个桶中装有 $a_i$ 升水。

你可以将水从一个桶倒入另一个桶。每次倒水操作中，你可以任选两个不同的桶 $x$ 和 $y$（其中第 $x$ 个桶不能为空），并将任意数量的水（可以是全部）从桶 $x$ 倒入桶 $y$。你可以假设所有桶的容量无限，因此每个桶中可容纳任意多的水。

在最多进行 $k$ 次倒水操作的前提下，求桶中水量最大值与最小值之间可能达到的最大差值。

一些示例：

• 若你有四个桶，每个桶初始均装有 $5$ 升水，且 $k = 1$，则你可以将第二个桶中的全部 $5$ 升水倒入第四个桶，此时各桶水量为 $[5, 0, 5, 10]$，最大值与最小值之差为 $10$；
• 若所有桶初始均为空，则无法进行任何操作，此时最大值与最小值之差仍为 $0$。

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \lt n \le 2 \cdot 10^5$) — the number of barrels and the number of pourings you can make.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{9}$), where $a_i$ is the initial amount of water the $i$-th barrel has.

It's guaranteed that the total sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$.

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

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \lt 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$。

For each test case, print the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most $k$ times.

对于每个测试用例，输出在最多倾倒 $k$ 次水的情况下，桶中水量的最大值与最小值之间可能达到的最大差值。