У Алисы и Боба есть \(n\) предметов, которые они хотят разделить между собой, поэтому они решили сыграть в игру. У каждого предмета есть стоимость: \(i\)-й предмет стоит \(a_i\). Игроки ходят по очереди, начиная с Алисы.
На каждом ходу игрок выбирает один из оставшихся предметов и забирает его. Игроки ходят, пока не закончатся все предметы.
Обозначим суммарную стоимость предметов, взятых Алисой, за \(A\), а суммарную стоимость предметов Боба за \(B\). Тогда итоговый счет игры будет равен \(A - B\).
Алиса хочет максимизировать счет, в то время как Боб хочет минимизировать его. Оба, Алиса и Боб, будут играть оптимально.
Однако игра состоится завтра, а потому сегодня Боб может немного изменить стоимости предметов. Он может увеличить стоимости \(a_i\) нескольких предметов (возможно, всех или ни одного) на целое значение (возможно одно и то же или на разное для каждого предмета). Однако, общее увеличение должно быть не более \(k\). В противном случае Алиса может заподозрить что-то неладное. Обратите внимание, что Боб не может уменьшать стоимости, только увеличивать.
Какого минимально возможного счета может достигнуть Боб?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально возможный счет \(A - B\), учитывая, что Боб заранее увеличит стоимости нескольких (возможно, всех или ни одного) предметов.
Примечание
В первом наборе Боб может увеличить \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 5
1 10
3 0
10 15 12
4 6
3 1 2 4
2 4
6 9
|
4
13
0
0
|