给定一个整数数组 $$$a_1, a_2, a_3, \dots, a_n$$$。您的任务是使 $$$a$$$ 的所有元素相等。为此,您最多可以执行以下操作 $$$k$$$ 次:
- 选择从 $$$1$$$ 到 $$$n$$$ 的任意索引 $$$i$$$ 并将 $$$a_i$$$ 加一。
在所有可能的使数组相等的方法中,您最多可以获得多少枚金币?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。接下来是 $$$t$$$ 案例(所有案例都是独立的)。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \le 10^{12}$$$) - 数组 $$$a$$$ 的大小以及可以执行的最大操作数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 数组本身。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,如果不可能使所有元素相等,则打印 $$$-1$$$。否则,打印在使所有元素相等的情况下您可以赚取的最大硬币数量。
示例
输入复制
43 161 10 24 206 2 4 95 97 7 7 7 72 10000000000001000000000 1000000000
输出复制
-1 11 0 499999999999
注意
在第一个测试用例中,您至少需要 $$$17$$$ 操作才能使所有元素相等(或获取数组 $$$[10, 10, 10]$$$)。
在第二个测试用例中,例如,您可以将 $$$a_3 = 4$$$ 增加到 $$$10$$$,然后将 $$$a_1 = 6$$$ 增加到 $$$10$$$,之后将 $$$a_4 = 9$$$ 增加到 $$$10$$$,最后将 $$$a_2 = 2$$$ 增加到$$$10$$$。您将执行 $$$19$$$ 操作并总共赚取 $$$(10 - 4) + (10 - 6) + (10 - 9) = 11$$$ 硬币,因为将 $$$a_2$$$ 从 $$$2$$$ 增加到 $$$10$$$ 不会给您任何硬币。
在第三个测试用例中,您可以保持数组不变或使所有元素等于 $$$8$$$ — 两种策略都会给您 $$$0$$$ 硬币。