D. 避开最小值

时间限制： 每测试 $2$ 秒
内存限制： 每测试 $256$ 兆字节

给你一个整数数组 $a_1, a_2, a_3, \dots, a_n$。你的任务是使 $a$ 的所有元素相等。为此，你最多可以执行 $k$ 次以下操作：

• 选择任意索引 $i$（从 $1$ 到 $n$），并将 $a_i$ 增加 $1$。

你可以选择数组中的任意元素，但如果选择的 $a_i$ 严格大于数组当前的最小值，你将获得一枚硬币。

在所有能使数组元素全部相等的操作方法中，你最多能获得多少枚硬币？

---

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 1000)$ — 测试用例的数量。接下来是 $t$ 个独立的测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ $(2 \leq n \leq 3 \cdot 10^5;\ 1 \leq k \leq 10^{12})$ — 数组 $a$ 的大小和你可以执行的最大操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq 10^9)$ — 数组本身。

保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

---

输出格式

对于每个测试用例，如果无法使所有元素相等，输出 $-1$。否则，输出在使所有元素相等的过程中能获得的最大硬币数量。

---

样例

输入

4
3 16
1 10 2
4 20
6 2 4 9
5 9
7 7 7 7 7
2 1000000000000
1000000000 1000000000

输出

-1
11
0
499999999999

---

样例解释

第一个测试用例：你需要至少 $17$ 次操作才能使所有元素相等（得到数组 $[10, 10, 10]$）。由于 $k = 16 < 17$，无法完成，输出 $-1$。

第二个测试用例：可以按如下方式操作，例如：

• 将 $a_3 = 4$ 增加到 $10$；
• 然后将 $a_1 = 6$ 增加到 $10$；
• 然后将 $a_4 = 9$ 增加到 $10$；
• 最后将 $a_2 = 2$ 增加到 $10$。

共执行 $19$ 次操作（$\leq k = 20$），获得的硬币总数为：

$$(10 - 4) + (10 - 6) + (10 - 9) = 6 + 4 + 1 = 11$$

因为将 $a_2$ 从 $2$ 增加到 $10$ 时，$2$ 始终是数组的最小值，不会获得硬币。

第三个测试用例：数组已经全部相等，你可以不做任何操作，或者将所有元素增加到 $8$——两种策略都获得 $0$ 枚硬币。

第四个测试用例：数组初始为 $[10^9, 10^9]$，已经相等。你可以将两者都增加至某个值，通过精心安排操作顺序，最多可获得 $499999999999$ 枚硬币。