B. Бочки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перед вами в ряд выстроены $$$n$$$ бочек, пронумерованные слева направо, начиная с единицы. В $$$i$$$-й бочке налито $$$a_i$$$ литров воды.

Вы можете переливать воду из одной бочки в другую. В ходе одного переливания вы можете выбрать две разные бочки с номерами $$$x$$$ и $$$y$$$ (бочка $$$x$$$ должна быть непустой) и перелить любое возможное количество воды из бочки $$$x$$$ в бочку $$$y$$$ (возможно, всю воду). Считайте, что каждая бочка имеет бесконечную емкость, то есть в бочку можно налить сколько угодно воды.

Определите максимальную разность между бочкой с наибольшим количество воды и бочкой с наименьшим количеством воды, если вы можете сделать не более $$$k$$$ переливаний.

Несколько примеров:

  • если у вас есть четыре бочки, в каждой из которых по $$$5$$$ литров воды, и $$$k = 1$$$, вы можете вылить $$$5$$$ литров из второй бочки в четвертую, тогда количества литров воды в бочках будут равны $$$[5, 0, 5, 10]$$$, и разность между максимальным и минимальным равна $$$10$$$;
  • если все бочки — пустые, вы не сможете сделать ни одного переливания, и разность между максимальным и минимальным количеством будет равна $$$0$$$.
Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$) — количество бочек и максимальное количество переливаний, которые вы можете произвести.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно изначальному количеству литров воды, которое находится в бочке номер $$$i$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

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

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