题目描述

有 $n$ 个水桶排成一排，从左到右编号为 $1$ 到 $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$ 次倒水操作的情况下，水桶中最多水量与最少水量的最大可能差值。

说明/提示

由 ChatGPT 4.1 翻译

样例

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

10
0