Alice 和 Bob 有 $$$n$$$ 件物品想要在他们之间分配,因此他们决定玩一个游戏。所有物品都有成本,第 $$$i$$$ 物品的成本为 $$$a_i$$$。玩家从爱丽丝开始轮流移动。
在每个回合中,玩家选择剩余的物品之一并拿走它。游戏继续进行,直到没有物品留下。
假设 $$$A$$$ 是 Alice 拿走的物品的总成本,$$$B$$$ 是 Bob 的物品的总成本。游戏的最终得分将等于 $$$A - B$$$。
Alice 想要最大化分数,而 Bob 想要最小化分数。 Alice 和 Bob 都会发挥最佳状态。
但比赛将于明天举行,所以今天鲍勃可以稍微修改一下费用。他可以将几个(可能没有或全部)项目的成本$$$a_i$$$增加一个整数值(可能每个项目增加相同的值或不同的值)。但是,总增量必须小于或等于 $$$k$$$。否则,爱丽丝可能会怀疑什么。请注意,鲍勃不能减少成本,只能增加成本。
Bob 能达到的最低分数是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。然后是 $$$t$$$ 案例。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le 10^9$$$) - 项目数量和 Bob 可以增加的最大总数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 物品的初始成本。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - Bob 增加了几个(可能没有或全部)项目的成本后的最低可能得分 $$$A - B$$$。
示例
输入 #1
4 2 5 1 10 3 0 10 15 12 4 6 3 1 2 4 2 4 6 9
输出 #1
4 13 0 0
注意
在第一个测试用例中,Bob 可以将 $$$a_1$$$ 增加 $$$5$$$,使成本等于 $$$[6, 10]$$$。明天,爱丽丝将拿走 $$$10$$$,鲍勃将拿走 $$$6$$$。总分等于 $$$10 - 6 = 4$$$,这是可能的最低分数。
在第二个测试用例中,Bob 无法更改成本。因此,分数将等于 $$$(15 + 10) - 12 = 13$$$,因为 Alice 将获得 $$$15$$$,Bob 将获得 $$$12$$$,而 Alice — $$$10$$$。
在第三个测试用例中,例如,Bob 可以将 $$$a_1$$$ 增加 $$$1$$$,将 $$$a_2$$$ 增加 $$$3$$$,将 $$$a_3$$$ 增加 $$$2$$$。总变化等于 $$$1 + 3 + 2 \le 6$$$,成本将等于 $$$[4, 4, 4, 4]$$$。显然,分数将等于 $$$(4 + 4) - (4 + 4) = 0$$$。
在第四个测试用例中,Bob 可以将 $$$a_1$$$ 增加 $$$3$$$,使成本等于 $$$[9, 9]$$$。分数将等于 $$$9 - 9 = 0$$$。