B2. K по цене одного (усложнённая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия этой задачи. Единственное отличие в ограничении на $$$k$$$ —количество подарков в акции. В этой версии $$$2 \le k \le n$$$.

Вася пришел в магазин, чтобы купить подарки для своих друзей на Новый год. Оказалось, что ему очень повезло — именно сегодня в магазине проводится акция «$$$k$$$ товаров по цене одного».

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

Более формально, для каждого подарка определена его цена $$$a_i$$$ — количество монет, которое нужно потратить, чтобы приобрести этот подарок. Изначально, у Васи есть $$$p$$$ монет. Он хочет приобрести максимальное количество подарков. Вася может сколько угодно раз выполнить одну из следующих операций.

  • Вася может купить один любой подарок с номером $$$i$$$, если у него в настоящий момент достаточно монет (то есть $$$p \ge a_i$$$). После покупки этого подарка, количество монет у Васи уменьшится на величину $$$a_i$$$, то есть становится $$$p := p - a_i$$$.
  • Вася может купить подарок с номером $$$i$$$, а также выбрать еще ровно $$$k-1$$$ подарков, цены которых не превосходят $$$a_i$$$, если у него в настоящий момент достаточно монет (то есть $$$p \ge a_i$$$). Таким образом он покупает все эти $$$k$$$ подарков, а его количество монет уменьшается на величину $$$a_i$$$, то есть становится $$$p := p - a_i$$$.

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

Например, если в магазине сейчас есть $$$n=5$$$ подарков, имеющих цены $$$a_1=2, a_2=4, a_3=3, a_4=5, a_5=7$$$ соответственно, $$$k=2$$$, а у Васи есть $$$6$$$ монет, то он может купить суммарно $$$3$$$ подарка. Подарок с номером $$$1$$$ Вася купит, не используя акцию, и заплатит $$$2$$$ монеты. Подарки с номерами $$$2$$$ и $$$3$$$ Вася купит используя акцию, и заплатит $$$4$$$ монеты. Можно доказать, что приобрести больше подарков, имея шесть монет, Вася не может.

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

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

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

Далее следуют описания $$$t$$$ наборов входных данных, по две строки на каждый набор.

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

Во второй строке каждого набора данных находятся $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^4$$$) — цены подарков.

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

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

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

Пример
Входные данные
8
5 6 2
2 4 3 5 7
5 11 2
2 4 3 5 7
3 2 3
4 2 6
5 2 3
10 1 3 9 2
2 10000 2
10000 10000
2 9999 2
10000 10000
4 6 4
3 2 3 2
5 5 3
1 2 2 1 2
Выходные данные
3
4
1
1
2
0
4
5