给你一个整数数组 $$$a_1, a_2, \dots, a_n$$$ 和整数 $$$k$$$。
只需一步,您就可以
- 选择某个索引 $$$i$$$ 并将 $$$a_i$$$ 减一(使 $$$a_i = a_i - 1$$$);
- 或选择两个索引 $$$i$$$ 和 $$$j$$$ 并将 $$$a_i$$$ 设置为等于 $$$a_j$$$ (使 $$$a_i = a_j$$$)。
计算数组 $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$ 的总和所需的最少步骤是多少? (允许将数组的值设为负数)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^{15}$$$) - 数组 $$$a$$$ 的大小及其总和的上限。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 数组本身。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 使 $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$ 的最小步骤数。
示例
输入 #1
4 1 10 20 2 69 6 9 7 8 1 2 1 3 1 2 1 10 1 1 2 3 1 2 6 1 6 8 10
输出 #1
10 0 2 7
注意
在第一个测试用例中,您应该减少 $$$a_1$$$ $$$10$$$ 次,以使总和低于或等于 $$$k = 10$$$。
在第二个测试用例中,数组 $$$a$$$ 的总和已经小于或等于 $$$69$$$,因此不需要更改它。
在第三个测试用例中,您可以例如:
1. 设置$$$a_4 = a_3 = 1$$$;
2. $$$a_4$$$减1,得到$$$a_4 = 0$$$。
在第四个测试用例中,您可以例如:
1.选择$$$a_7$$$并减少$$$3$$$倍;你会得到 $$$a_7 = -2$$$;
2. 选择$$$4$$$元素$$$a_6$$$、$$$a_8$$$、$$$a_9$$$和$$$a_{10}$$$并且它们等于$$$a_7 = -2$$$。