Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

A. Жадный Монокарп
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ сундуков; $$$i$$$-й сундук изначально содержит $$$a_i$$$ монет. Для каждого сундука вы можете выбрать любое неотрицательное ($$$0$$$ или больше) количество монет, чтобы добавить в этот сундук, с одним ограничением: суммарное количество монет во всех сундуках должно стать не менее $$$k$$$.

После того как вы закончите добавлять монеты в сундуки, придет жадный Монокарп, которому нужны монеты. Он будет брать сундуки по одному, и поскольку он жадный, он всегда будет выбирать сундук с максимальным количеством монет. Монокарп остановится, как только общее количество монет в сундуках, которые он забрал, станет не менее $$$k$$$.

Вы хотите, чтобы Монокарп забрал как можно меньше монет, поэтому вам нужно добавлять монеты в сундуки таким образом, чтобы, когда Монокарп закончит забирать сундуки, у него было ровно $$$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$$$).
Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество монет, которое нужно добавить, чтобы, когда Монокарп закончит забирать сундуки, у него было ровно $$$k$$$ монет. Можно показать, что при данных ограничениях задачи это всегда возможно.

Пример
Входные данные
4
5 4
4 1 2 3 2
5 10
4 1 2 3 2
2 10
1 1
3 8
3 3 3
Выходные данные
0
1
8
2
Примечание

В первом примере не нужно добавлять монеты. Когда Монокарп придет, он возьмет сундук с $$$4$$$ монетами, так что у него будет ровно $$$4$$$ монеты.

Во втором примере вы можете добавить $$$1$$$ монету в $$$4$$$-й сундук, так что, когда Монокарп придет, он возьмет сундук с $$$4$$$ монетами, затем еще один сундук с $$$4$$$ монетами и сундук с $$$2$$$ монетами.

В третьем примере вы можете добавить $$$3$$$ монеты в $$$1$$$-й сундук и $$$5$$$ монет во $$$2$$$-й сундук.

В четвертом примере вы можете добавить $$$1$$$ монету в $$$1$$$-й сундук и $$$1$$$ монету в $$$3$$$-й сундук.