← 返回题目列表

Codeforces · 2042/A

A. 贪婪的单果树

中文机器翻译题面 查看原题

有$$$n$$$箱子;第 $$$i$$$ 个箱子最初包含 $$$a_i$$$ 硬币。对于每个箱子,您可以选择任何非负($$$0$$$ 或更多)数量的硬币添加到该箱子中,但有一个限制:所有箱子中的硬币总数必须至少为 $$$k$$$。

当你向箱子里添加完金币后,贪婪的 Monocarp 就会来,他想要金币。他会一一拿走箱子,由于他很贪心,所以他总是会选择硬币数量最多的箱子。一旦他拿走的箱子中的金币总数至少为 $$$k$$$,Monocarp 就会停止。

你希望 Monocarp 拿走尽可能少的硬币,所以你必须以这样的方式向箱子添加硬币,这样,当 Monocarp 停止拿走箱子时,他将恰好拥有 $$$k$$$ 硬币。计算您需要添加的最少硬币数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例由两行组成:

- 第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 50$$$; $$$1 \le k \le 10^7$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$)。

输出

对于每个测试用例,打印一个整数 - 您必须添加的最小硬币数量,以便当 Monocarp 停止拿走箱子时,他正好拥有 $$$k$$$ 硬币。可以证明,在问题的约束下,总是可能的。

示例

输入 #1

4
5 4
4 1 2 3 2
5 10
4 1 2 3 2
2 10
1 1
3 8
3 3 3

输出 #1

0
1
8
2

注意

在示例的第一个测试用例中,您不必添加任何硬币。当 Monocarp 到达时,他会拿走装有 $$$4$$$ 硬币的箱子,因此他将恰好拥有 $$$4$$$ 硬币。

在示例的第二个测试用例中,您可以将 $$$1$$$ 硬币添加到第 $$$4$$$ 个箱子中,因此,当 Monocarp 到达时,他会拿走一个装有 $$$4$$$ 硬币的箱子,然后是另一个装有 $$$4$$$ 硬币的箱子,最后是一个装有 $$$2$$$ 硬币的箱子。

在示例的第三个测试用例中,您可以将 $$$3$$$ 硬币添加到 $$$1$$$-st 箱子中,将 $$$5$$$ 硬币添加到 $$$2$$$-nd 箱子中。

在示例的第四个测试用例中,您可以将 $$$1$$$ 硬币添加到 $$$1$$$-st 箱子中,并将 $$$1$$$ 硬币添加到 $$$3$$$-rd 箱子中。