У Алисы и Боба есть $$$n$$$ предметов, которые они хотят разделить между собой, поэтому они решили сыграть в игру. У каждого предмета есть стоимость: $$$i$$$-й предмет стоит $$$a_i$$$. Игроки ходят по очереди, начиная с Алисы.
На каждом ходу игрок выбирает один из оставшихся предметов и забирает его. Игроки ходят, пока не закончатся все предметы.
Обозначим суммарную стоимость предметов, взятых Алисой, за $$$A$$$, а суммарную стоимость предметов Боба за $$$B$$$. Тогда итоговый счет игры будет равен $$$A - B$$$.
Алиса хочет максимизировать счет, в то время как Боб хочет минимизировать его. Оба, Алиса и Боб, будут играть оптимально.
Однако игра состоится завтра, а потому сегодня Боб может немного изменить стоимости предметов. Он может увеличить стоимости $$$a_i$$$ нескольких предметов (возможно, всех или ни одного) на целое значение (возможно одно и то же или на разное для каждого предмета). Однако, общее увеличение должно быть не более $$$k$$$. В противном случае Алиса может заподозрить что-то неладное. Обратите внимание, что Боб не может уменьшать стоимости, только увеличивать.
Какого минимально возможного счета может достигнуть Боб?
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следуют сами $$$t$$$ наборов.
В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le 10^9$$$) — количество предметов и максимальное общее увеличение, которое может сделать Боб.
Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — первоначальные стоимости предметов.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимально возможный счет $$$A - B$$$, учитывая, что Боб заранее увеличит стоимости нескольких (возможно, всех или ни одного) предметов.
42 51 103 010 15 124 63 1 2 42 46 9
4 13 0 0
В первом наборе Боб может увеличить $$$a_1$$$ на $$$5$$$, сделав стоимости равными $$$[6, 10]$$$. Завтра Алиса возьмет $$$10$$$, а Боб возьмет $$$6$$$. Общий счет будет равен $$$10 - 6 = 4$$$, и это минимально возможный результат.
Во втором наборе Боб не может изменять стоимости. Таким образом, итоговый счет будет равен $$$(15 + 10) - 12 = 13$$$, поскольку Алиса возьмет $$$15$$$, Боб возьмет $$$12$$$, а Алиса — $$$10$$$.
В третьем наборе Боб, например, может увеличить $$$a_1$$$ на $$$1$$$, $$$a_2$$$ на $$$3$$$ и $$$a_3$$$ на $$$2$$$. Общее изменение равно $$$1 + 3 + 2 \le 6$$$, и стоимости будут равны $$$[4, 4, 4, 4]$$$. Очевидно, что счет будет равен $$$(4 + 4) - (4 + 4) = 0$$$.
В четвертом наборе Боб может увеличить $$$a_1$$$ на $$$3$$$, сделав стоимости равными $$$[9, 9]$$$. Счет будет равен $$$9 - 9 = 0$$$.
Название |
---|