This is the hard version of this problem. The only difference is the constraint on $k$ — the number of gifts in the offer. In this version: $2 \le k \le n$.

Vasya came to the store to buy goods for his friends for the New Year. It turned out that he was very lucky — today the offer "$k$ of goods for the price of one" is held in store.

Using this offer, Vasya can buy exactly $k$ of any goods, paying only for the most expensive of them. Vasya decided to take this opportunity and buy as many goods as possible for his friends with the money he has.

More formally, for each good, its price is determined by $a_i$ — the number of coins it costs. Initially, Vasya has $p$ coins. He wants to buy the maximum number of goods. Vasya can perform one of the following operations as many times as necessary:

  Vasya can buy one good with the index $i$ if he currently has enough coins (i.e $p \ge a_i$). After buying this good, the number of Vasya's coins will decrease by $a_i$, (i.e it becomes $p := p - a_i$).  Vasya can buy a good with the index $i$, and also choose exactly $k-1$ goods, the price of which does not exceed $a_i$, if he currently has enough coins (i.e $p \ge a_i$). Thus, he buys all these $k$ goods, and his number of coins decreases by $a_i$ (i.e it becomes $p := p - a_i$). 

Please note that each good can be bought no more than once.

For example, if the store now has $n=5$ goods worth $a_1=2, a_2=4, a_3=3, a_4=5, a_5=7$, respectively, $k=2$, and Vasya has $6$ coins, then he can buy $3$ goods. A good with the index $1$ will be bought by Vasya without using the offer and he will pay $2$ coins. Goods with the indices $2$ and $3$ Vasya will buy using the offer and he will pay $4$ coins. It can be proved that Vasya can not buy more goods with six coins.

Help Vasya to find out the maximum number of goods he can buy.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The next lines contain a description of $t$ test cases. 

The first line of each test case contains three integers $n, p, k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le p \le 2\cdot10^9$, $2 \le k \le n$) — the number of goods in the store, the number of coins Vasya has and the number of goods that can be bought by the price of the most expensive of them.

The second line of each test case contains $n$ integers $a_i$ ($1 \le a_i \le 10^4$) — the prices of goods.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case in a separate line print one integer $m$ — the maximum number of goods that Vasya can buy.


-----Example-----
Input
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

Output
3
4
1
1
2
0
4
5

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Greedy algorithms


Solutions:
import sys
input = sys.stdin.buffer.readline

def getMinCost(nItems):
	idx = nItems - 1
	cost = 0
	if idx >= k - 1:
		cost += kBatchSum[idx]
		idx = (idx + 1) % k - 1
	if idx >= 0:
		cost += aSum[idx]
	return cost
t = int(input())
for _ in range(t):
	(n, p, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	aSum = [0 for _ in range(n)]
	kBatchSum = [0 for _ in range(n)]
	for (i, x) in enumerate(a):
		aSum[i] += x
		if i > 0:
			aSum[i] += aSum[i - 1]
		kBatchSum[i] += a[i]
		if i - k >= 0:
			kBatchSum[i] += kBatchSum[i - k]
		if i + 1 - k < 0:
			kBatchSum[i] = 0
	ans = 0
	for nItems in range(n + 1):
		if getMinCost(nItems) <= p:
			ans = nItems
	print(ans)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	ans = 0
	sm = 0
	ct = 0
	for i in range(k + 1):
		if i >= len(a):
			break
		if sm > p:
			break
		ct = i
		pseudocost = sm
		j = i + k - 1
		while j < n:
			if p >= pseudocost + a[j]:
				pseudocost += a[j]
				ct += k
			else:
				break
			j += k
		sm += a[i]
		ans = max(ans, ct)
	print(ans)


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if p < a[0]:
		print(0)
		continue
	dp = [[0, 0] for i in range(n + 1)]
	dp[0][1] = p
	dp[1][0] = 1
	dp[1][1] = p - a[0]
	for i in range(2, n + 1):
		if dp[i - 1][1] >= a[i - 1]:
			dp[i][0] = max(dp[i][0], dp[i - 1][0] + 1)
			dp[i][1] = dp[i - 1][1] - a[i - 1]
		if i >= k and dp[i - k][1] >= a[i - 1]:
			dp[i][0] = max(dp[i][0], dp[i - k][0] + k)
			dp[i][1] = dp[i - k][1] - a[i - 1]
	ans = 0
	for i in range(1, n + 1):
		ans = max(ans, dp[i][0])
	print(ans)


for _ in range(int(input())):
	(n, p, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	a.sort()
	dp = [0] * n
	ans = 0
	for i in range(k - 1):
		dp[i] = a[i] + dp[i - 1]
		if dp[i] <= p:
			ans = 1 + i
	for i in range(k - 1, n):
		dp[i] = a[i] + dp[i - k]
		if dp[i] <= p:
			ans = i + 1
	print(ans)


q = int(input())

def binarySearch(arr, l, r, x):
	if 1 <= len(arr[l:r + 1]) <= 2:
		return l
	if r >= l:
		mid = int(l + (r - l) / 2)
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binarySearch(arr, l, mid - 1, x)
		else:
			return binarySearch(arr, mid + 1, r, x)
	else:
		return -1

def solve():
	(n, pr, k) = map(int, input().split())
	L = list(map(int, input().split()))
	L.sort()
	dp = [0] * n
	ans = 0
	for i in range(0, k - 1):
		dp[i] += dp[i - 1] + L[i]
	for i in range(k - 1, n):
		if i == k - 1:
			dp[i] += L[i]
		else:
			dp[i] += dp[i - k] + L[i]
	for i in range(n):
		if dp[i] <= pr:
			ans = i + 1
	print(ans)
while q:
	solve()
	q -= 1


def go():
	(n, p, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	cost = [0] * (n + 1)
	for i in range(1, k):
		cost[i] = a[i - 1] + cost[i - 1]
	for i in range(k, n + 1):
		cost[i] = a[i - 1] + cost[i - k]
	while cost[n] > p:
		n -= 1
	return n
t = int(input())
for _ in range(t):
	print(go())


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	dp = [0] * (n + 1)
	a.sort()
	dp[1] = a[0]
	for i in range(1, n):
		x = a[i] + dp[i]
		if i + 1 >= k:
			y = a[i] + dp[i - k + 1]
		else:
			y = 10 ** 18
		cost = min(x, y)
		dp[i + 1] = cost
	for i in range(len(dp) - 1, -1, -1):
		if dp[i] <= p:
			print(i)
			break


sas = [1, 2, 3]
t = int(input())
for i in range(t):
	(n, p, k) = map(int, input().split())
	mas = list(map(int, input().split()))
	mas.sort()
	l = 0
	r = n

	def check(m):
		if m % k != 0:
			sm = 0
			i = m % k + k - 1
			while i < m:
				sm += mas[i]
				i += k
			return sum(mas[0:m % k]) + sm <= p
		else:
			sm = 0
			i = k - 1
			while i < m:
				sm += mas[i]
				i += k
			return sm <= p
	st = [0]
	i = k
	while i <= n:
		st.append(i)
		i += k
	l = 0
	r = len(st) - 1
	while r - l > 1:
		m = (l + r) // 2
		if check(st[m]):
			l = m
		else:
			r = m
	sas = 0
	if check(st[r]):
		sas = st[r]
	else:
		sas = st[l]
	l = sas
	r = min(sas + k - 1, n)
	while r - l > 1:
		m = (l + r) // 2
		if check(m):
			l = m
		else:
			r = m
	if check(r):
		print(r)
		continue
	if check(l):
		print(l)
		continue
	print(0)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	ar = sorted(ar)
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		if i < k:
			dp[i] = dp[i - 1] + ar[i - 1]
		else:
			dp[i] = min(dp[i - 1], dp[i - k]) + ar[i - 1]
	ans = 0
	for i in range(n + 1):
		if dp[i] <= p:
			ans = i
	print(ans)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	arr.sort()
	ans = 0
	tempans = 0
	for qw in range(k):
		ptemp = p
		tempans = qw
		for i in range(qw + k - 1, n, k):
			ptemp -= arr[i]
			if ptemp >= 0:
				tempans += k
			else:
				break
		ans = max(tempans, ans)
		p -= arr[qw]
		if p < 0:
			break
	print(ans)


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
for _ in range(int(inp())):
	(n, p, k) = mp()
	arr = lmp()
	arr.sort()
	ans = 0
	pre = [0]
	c = 0
	for i in range(k):
		c += arr[i]
		pre.append(c)
	i = 0
	while i < k and pre[i] <= p:
		x = pre[i]
		acm = i
		for j in range(i + k - 1, n, k):
			if x + arr[j] > p:
				break
			x += arr[j]
			acm += k
		ans = max(ans, acm)
		i += 1
	print(ans)


for tcase in range(int(input())):
	(nitems, coins, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls.sort()
	if ls[0] > coins:
		print(0)
		continue
	best = 0
	cumsum = 0
	for offset in range(k):
		if offset >= nitems or cumsum > coins:
			break
		spent = cumsum
		ptr = offset
		while ptr + k - 1 < nitems and ls[ptr + k - 1] + spent <= coins:
			spent += ls[ptr + k - 1]
			ptr += k
		best = max(best, ptr)
		cumsum += ls[offset]
	print(best)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a = sorted(a)
	dp = [0]
	for i in range(k - 1):
		dp.append(dp[-1] + a[i])
	for i in range(k - 1, n):
		dp.append(dp[i - k + 1] + a[i])
	ans = 0
	for i in range(1, n + 1):
		if dp[i] <= p:
			ans = i
	print(ans)


t = int(input())
for i in range(t):
	(n, p, k) = list(map(int, input().split(' ')))
	goods = sorted(list(map(int, input().split(' '))))
	numof_goods = [0 for i in range(n)]
	coins = [0 for i in range(n)]
	coins[0] = p - goods[0]
	numof_goods[0] = int(coins[0] >= 0)
	for i in range(n):
		if i == 0:
			continue
		if i + 1 > k:
			coins[i] = coins[i - k] - goods[i]
			if coins[i] >= 0:
				numof_goods[i] = numof_goods[i - k] + k
		elif i + 1 == k:
			coins[i] = p - goods[i]
			if coins[i] >= 0:
				numof_goods[i] = k
		else:
			coins[i] = coins[i - 1] - goods[i]
			if coins[i] >= 0:
				numof_goods[i] = numof_goods[i - 1] + 1
	print(max(numof_goods))


import os
from io import BytesIO

def check(x, p):
	i = x - 1
	while i > -1 and a[i] <= p:
		p -= a[i]
		if i >= k - 1:
			i -= k
		else:
			i -= 1
	return i <= -1
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = sorted(map(int, input().split()))
	dp = [1000000000] * (n + 1)
	dp[0] = 0
	ans = 0
	for i in range(1, n + 1):
		dp[i] = dp[i - 1] + a[i - 1]
		if i - k + 1 >= 0:
			dp[i] = min(dp[i], dp[i - k] + a[i - 1])
		if dp[i] <= p:
			ans = i
	print(ans)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	dp = [0 for i in range(n + 1)]
	a.sort()
	for i in range(1, n + 1):
		dp[i] = dp[i - 1] + a[i - 1]
		if i >= k:
			dp[i] = min(dp[i], dp[i - k] + a[i - 1])
	itr = n
	while itr >= 0:
		if dp[itr] <= p:
			break
		itr -= 1
	if itr == -1:
		itr += 1
	print(itr)


T = int(input())
for _ in range(T):
	(n, amt, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l = sorted(l)
	dp = [0] * (n + 1)
	ans = 0
	for i in range(n):
		if i - k >= -1:
			dp[i] = dp[i - k] + l[i]
		else:
			dp[i] = l[i] + dp[i - 1]
	for i in range(n):
		if dp[i] <= amt:
			ans = i + 1
	print(ans)


t = int(input())
for i in range(t):
	(n, p, k) = map(int, input().split())
	goods = list(map(int, input().split()))
	goods.sort()
	if goods[0] > p:
		print(0)
		continue
	elif len(goods) == 1:
		print(1)
		continue
	sums = [[0]]
	for i in range(k - 1):
		sums.append([sums[-1][0] + goods[i]])
	for i in range(k, n + 1):
		sums[i % k].append(sums[i % k][-1] + goods[i - 1])
	for i in range(n - 1, -1, -1):
		cost = sums[(i + 1) % k][(i + 1) // k]
		if cost <= p:
			print(i + 1)
			break


import sys
import math
from collections import defaultdict, Counter
import bisect
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for i in range(t):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	pre = [0] * (n + 1)
	pre[0] = a[0]
	for j in range(1, n):
		pre[j] = pre[j - 1] + a[j]
	p1 = p
	main = 0
	for kk in range(k):
		ans = 0
		if p >= pre[kk - 1]:
			p -= pre[kk - 1]
			ans += kk
			for j in range(k - 1 + kk, n, k):
				if p - a[j] >= 0:
					ans += k
					p -= a[j]
				else:
					for jj in range(j - k + 1, j):
						if p >= a[jj]:
							p -= a[jj]
							ans += 1
						else:
							break
					break
			main = max(main, ans)
			p = p1
		else:
			break
	print(main)


from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))

def input():
	return stdin.readline().strip()

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (fast, lambda : map(int, z().split()))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer, end='\n'):
	stdout.write(str(answer) + end)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
num = int(z())
for i in range(num):
	(n, p, k) = zzz()
	arr = szzz()
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		dp[i] = dp[i - 1] + arr[i - 1]
		if i >= k:
			dp[i] = dp[i - k] + arr[i - 1]
	for i in range(n, -1, -1):
		if dp[i] <= p:
			print(i)
			break


for _ in range(int(input())):
	(n, p, k) = list(map(int, input().split()))
	array = list(map(int, input().split()))
	array.sort()
	dp = [0]
	pre = 0
	for i in range(k - 1):
		pre += array[i]
		dp.append(pre)
	for i in range(k - 1, n):
		dp.append(array[i] + dp[i - k + 1])
	ans = 0
	for i in range(1, n + 1):
		if dp[i] <= p:
			ans = i
	print(ans)


def f(p, k, a):
	a = [0] + a
	dp = [0] * (len(a) + 1)
	a = sorted(a)
	for i in range(1, len(a)):
		dp[i] = dp[i - 1] + a[i]
		if i >= k:
			dp[i] = min(dp[i], a[i] + dp[i - k])
	ans = 0
	for i in range(1, len(a)):
		if dp[i] <= p:
			ans = i
	return ans
for _ in range(int(input())):
	(n, p, k) = map(int, input().strip().split())
	lst = list(map(int, input().strip().split()))
	print(f(p, k, lst))


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.sort()
	prefix_sums = [0]
	for a_i in a[:k]:
		prefix_sums.append(a_i + prefix_sums[-1])
	max_goods = 0
	for (ind, start_sum) in enumerate(prefix_sums):
		balance = p - start_sum
		local_goods = ind
		flag = 0
		while ind + k <= n and a[ind + k - 1] <= balance:
			balance -= a[ind + k - 1]
			ind += k
			local_goods += k
			flag = 1
		if balance >= 0:
			max_goods = max(max_goods, local_goods)
	print(max_goods)


t = int(input())
while t:
	t -= 1
	(n, p, k) = [int(x) for x in input().split()]
	li = [int(x) for x in input().split()]
	dp = [0] * (n + 1)
	li.sort()
	dp[0] = p
	for i in range(1, min(k - 1, n) + 1):
		if dp[i - 1] - li[i - 1] >= 0 and dp[i - 1] != -1:
			dp[i] = dp[i - 1] - li[i - 1]
		else:
			dp[i] = -1
	flag = 0
	for i in range(k, n + 1):
		if dp[i - k] >= li[i - 1]:
			dp[i] = dp[i - k] - li[i - 1]
		else:
			dp[i] = -1
	ans = 0
	for i in range(0, n + 1):
		if dp[i] != -1:
			ans = i
	print(ans)


import sys
reader = (map(int, line.split()) for line in sys.stdin)

def func(a, n, p, k):
	D = [0] * (n + 1)
	for i in range(1, k):
		D[i] = D[i - 1] + a[i - 1]
	for i in range(k, n + 1):
		D[i] = D[i - k] + a[i - 1]
	for i in range(n, -1, -1):
		if D[i] <= p:
			return i
(t,) = next(reader)
for _ in range(t):
	(n, p, k) = next(reader)
	a = list(next(reader))
	a.sort()
	ans = func(a, n, p, k)
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for tt in range(t):
	(n, p, k) = [int(x) for x in input().strip().split()]
	a = sorted([0] + [int(x) for x in input().strip().split()])
	account_cumsum = [0 for _ in range(n + 1)]
	count_cumsum = [0 for _ in range(n + 1)]
	for i in range(1, k):
		if account_cumsum[i - 1] + a[i] <= p:
			account_cumsum[i] = account_cumsum[i - 1] + a[i]
			count_cumsum[i] = count_cumsum[i - 1] + 1
		else:
			account_cumsum[i] = account_cumsum[i - 1]
			count_cumsum[i] = count_cumsum[i - 1]
	else:
		for i in range(k, n + 1):
			if account_cumsum[i - k] + a[i] <= p:
				account_cumsum[i] = account_cumsum[i - k] + a[i]
				count_cumsum[i] = count_cumsum[i - k] + k
	print(max(count_cumsum))


from sys import stdin, stdout
from math import *
for __ in range(int(input())):
	(a, b, c) = map(int, input().split())
	l = list(map(int, input().split()))
	bb = b
	p = [0]
	l.sort()
	for i in range(a):
		p.append(l[i] + p[-1])
	l.append(99999999999)
	count = []
	for ii in range(c + 1):
		count1 = 0
		b = bb
		if p[ii] <= b:
			count1 += ii
			b -= p[ii]
		i = ii
		while i < a:
			if i + c - 1 < a and b >= l[i + c - 1]:
				b -= l[i + c - 1]
				count1 += c
				i += c
			else:
				break
		count.append(count1)
	print(max(count))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	t = int(input())
	for _ in range(t):
		(n, p, k) = map(int, input().split())
		a = sorted([int(i) for i in input().split()])
		u = 0
		s = 0
		pref = [[0] * ((n - i) // k + 1) for i in range(k)]
		for i in range(k - 1, n):
			pref[(i + 1) % k][(i + 1) // k] = pref[(i + 1) % k][(i + 1) // k - 1] + a[i]
			if (i + 1) % k == 0 and pref[(i + 1) % k][(i + 1) // k] <= p:
				u = pref[(i + 1) % k][(i + 1) // k]
				s = i + 1
		rs = s
		for i in range(1, k):
			if s // k >= len(pref[i]):
				break
			u = u - pref[i - 1][s // k] + pref[i][s // k] + a[i - 1]
			if u <= p:
				rs = s + i
		print(rs)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	dp = [0] * n
	for i in range(n):
		if i >= k - 1:
			dp[i] = a[i] + dp[i - k]
			if dp[i] <= p:
				ans = i + 1
		else:
			dp[i] = a[i] + dp[i - 1]
			if dp[i] <= p:
				ans = max(ans, i + 1)
	print(ans)


from sys import stdin, stdout

def find(a, s, c, n, j):
	for i in range(j + k - 1, n, k):
		if a[i] <= s:
			s -= a[i]
			c += k
		else:
			break
	return c
t = stdin.readline()
t = int(t)
while t > 0:
	(n, s, k) = [int(i) for i in stdin.readline().split()]
	a = [int(i) for i in stdin.readline().split()]
	a = sorted(a)
	ans = 0
	tans = 0
	su = 0
	ans = max(ans, find(a, s, 0, n, 0))
	if sum(a) <= s:
		ans = n
		tans = 'cv'
	for i in range(k - 1):
		if tans == 'cv':
			break
		if a[0] > s:
			break
		su += a[i]
		if su > s:
			tans = i
			ans = max(ans, tans)
			break
		else:
			ans = max(ans, find(a, s - su, i + 1, n, i + 1))
	stdout.write(str(ans))
	stdout.write('\n')
	t -= 1


import sys
input = sys.stdin.readline
t = int(input())
for testcases in range(t):
	(n, p, k) = map(int, input().split())
	A = sorted(map(int, input().split()))
	S = [0] * (n + k + 3)
	for i in range(k - 1):
		S[i] = A[i] + S[i - 1]
	for i in range(k - 1, n):
		S[i] = S[i - k] + A[i]
	ANS = -1
	for i in range(n):
		if S[i] <= p:
			ANS = i
	print(ANS + 1)


from collections import Counter
from collections import defaultdict
import math

def inp():
	return map(int, input().split())
mod = int(1000000000.0) + 7
for _ in range(int(input())):
	(n, p, k) = inp()
	a = list(inp())
	dp = [0] * (n + 1)
	a.sort()
	for i in range(1, n + 1):
		if i < k:
			dp[i] = dp[i - 1] + a[i - 1]
		elif i >= k:
			dp[i] = dp[i - k] + a[i - 1]
	ans = 0
	for i in range(n, -1, -1):
		if dp[i] <= p:
			ans = i
			break
	print(ans)


a = int(input())
for i in range(a):
	(b, m, k) = map(int, input().split(' '))
	c = list(map(int, input().split(' ')))
	c.sort()
	cost = [0] * (b + 1)
	for l in range(1, k):
		cost[l] = c[l - 1] + cost[l - 1]
	for j in range(k, b + 1):
		cost[j] = cost[j - k] + c[j - 1]
	for n in range(b + 1):
		if cost[n] <= m:
			ans = n
	print(ans)


for _ in [0] * int(input()):
	(n, p, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	pref = 0
	ans = 0
	for i in range(k + 1):
		sum = pref
		if sum > p:
			break
		cnt = i
		for j in range(i + k - 1, n, k):
			if sum + a[j] <= p:
				cnt += k
				sum += a[j]
			else:
				break
		if i < n:
			pref += a[i]
		ans = max(ans, cnt)
	print(ans)


for n in range(int(input())):
	(_, p, k) = map(int, input().split())
	c = map(int, input().split())
	c = sorted(c)
	i = 0
	pre = 0
	ans = 0
	while i < len(c) and i < k and (pre <= p):
		j = i + k - 1
		dis = 0
		while j < len(c) and dis + pre + c[j] <= p:
			dis += c[j]
			j += k
		pre += c[i]
		ans = max(ans, j - k + 1)
		i += 1
	print(ans)


import sys
input = sys.stdin.readline
a = int(input())
for i in range(a):
	(n, p, k) = map(int, input().split())
	z = list(map(int, input().split()))
	z.sort()
	ans = [0]
	for i in range(len(z)):
		ans.append(ans[-1] + z[i])
	dp = [0 for i in range(len(ans))]
	for i in range(len(ans)):
		if i < k:
			dp[i] = ans[i]
		else:
			dp[i] = dp[i - k] + z[i - 1]
	save = 0
	for i in range(len(dp) - 1, -1, -1):
		if dp[i] <= p:
			save = i
			break
	print(save)


import math as mt
import bisect
import sys
input = sys.stdin.readline
t = int(input())
import collections
import heapq
p = 10 ** 9 + 7

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def solve():
	dp = [0 for i in range(n + 1)]
	ans = 0
	cnt = 0
	l.sort()
	for i in range(k - 1):
		if l[i] + cnt <= x:
			dp[i] = l[i] + cnt
			ans = i + 1
			cnt += l[i]
		else:
			break
	if l[k - 1] <= x:
		dp[k - 1] = l[k - 1]
		ans = k
	else:
		return ans
	for i in range(k, n):
		if dp[i - k] == 0:
			dp[i] = 0
		elif dp[i - k] + l[i] <= x:
			dp[i] = dp[i - k] + l[i]
			ans = i + 1
	return ans
for _ in range(t):
	(n, x, k) = map(int, input().split())
	l = list(map(int, input().split()))
	print(solve())


def main():
	t = int(input())
	for T in range(t):
		(n, p, k) = [int(i) for i in input().split()]
		li = sorted([int(i) for i in input().split()])
		price = 0
		pre = [0] * (len(li) + 1)
		for i in range(len(li)):
			if i >= k - 1:
				temp = li[i] + pre[i - k + 1]
				pre[i + 1] = temp
				if pre[i + 1] <= p:
					price = i + 1
			else:
				pre[i + 1] = li[i] + pre[i]
				if pre[i + 1] <= p:
					price += 1
		print(price)
main()


import sys
for _ in range(int(input())):
	(n, p, k) = map(int, input().strip().split())
	A = list([int(x) for x in sys.stdin.readline().strip().split()])
	A.sort()
	dp = [0] * k
	dp[0] = 0
	r = 0
	for i in range(1, k):
		dp[i] = A[i - 1] + dp[i - 1]
		if dp[i] <= p:
			r = i
	for i in range(k):
		s = dp[i]
		j = i + k
		while j <= n and s + A[j - 1] <= p:
			r = max(j, r)
			s += A[j - 1]
			j = j + k
	print(r)


import sys
import math, bisect, operator
(inf, m) = (float('inf'), 10 ** 9 + 7)
sys.setrecursionlimit(10 ** 5)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.readline())
neo = lambda : map(int, sys.stdin.readline().split())
Neo = lambda : list(map(int, sys.stdin.readline().split()))
for _ in range(I()):
	(n, p, k) = neo()
	A = Neo()
	A.sort()
	dp = [0]
	for i in range(k - 1):
		dp += [dp[-1] + A[i]]
	for i in range(k - 1, n):
		dp += [min(dp[-1] + A[i], dp[-k] + A[i])]
	for i in range(n, -1, -1):
		if dp[i] <= p:
			print(i)
			break
	else:
		print(0)


t = int(input())
for test in range(t):
	(n, p, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	sum1 = [0] * (n + 1)
	ans = 0
	sum1[0] = 0
	sum1[1] = l[0]
	if sum1[1] <= p:
		ans = 1
	for i in range(2, k):
		sum1[i] = sum1[i - 1] + l[i - 1]
		if sum1[i] <= p:
			ans = i
	for i in range(k, n + 1):
		sum1[i] = sum1[i - k] + l[i - 1]
		if sum1[i] <= p:
			ans = i
	print(ans)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import time
start_time = time.time()
import collections as col
import math, string
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	(N, P, K) = getInts()
	A = getInts()
	A.sort()
	if P < A[0]:
		return 0
	ans = 0
	prefs = [0]
	for a in A:
		prefs.append(prefs[-1] + a)
	prefs = prefs[1:]
	for idx in range(K - 1, 2 * K - 1):
		if idx > N - 1:
			break
		if A[idx] > P:
			right = idx - 1
			if right < 0:
				continue
			elif prefs[right] <= P:
				ans = max(ans, right + 1)
			elif prefs[0] > P:
				continue
			else:
				left = 0
				while right - left > 1:
					middle = (left + right) // 2
					if prefs[middle] <= P:
						left = middle
					else:
						right = middle
				ans = max(ans, right)
			continue
		start = idx
		money = P
		while idx < N and A[idx] <= money:
			money -= A[idx]
			idx += K
		idx -= K
		tmp = idx - start + K
		extra = 0
		right = start - K
		if right < 0:
			extra = 0
		elif prefs[right] <= money:
			extra = right + 1
		elif prefs[0] > money:
			extra = 0
		else:
			left = 0
			while right - left > 1:
				middle = (left + right) // 2
				if prefs[middle] <= money:
					left = middle
				else:
					right = middle
			extra = right
		ans = max(ans, extra + tmp)
	return ans
for _ in range(getInt()):
	print(solve())


import sys
t = int(sys.stdin.readline().rstrip())

def main():
	for _ in range(t):
		(n, p, k) = map(int, sys.stdin.readline().split())
		(*a,) = map(int, sys.stdin.readline().split())
		a.sort()
		cnt = 0
		cost = 0
		for i in range(k - 1, n, k):
			if cost + a[i] <= p:
				cost += a[i]
				cnt += k
			else:
				r = i - k
				break
		else:
			r = k * (n // k) - 1
		j = 0
		tmp_cost = 0
		while r + j < n - 1:
			j += 1
			cost = sum(a[k - 1 + j:r + j + 1:k]) + tmp_cost
			if cost > p:
				yield cnt
				break
			if cost + a[j - 1] <= p:
				tmp_cost += a[j - 1]
				cnt += 1
			else:
				yield cnt
				break
		else:
			yield n
ans = main()
print(*ans, sep='\n')


t = int(input())
for j in range(t):
	(n, p, k) = map(int, input().split())
	l = input().split()
	for j1 in range(len(l)):
		l[j1] = int(l[j1])
	l.sort()
	ans = [0 for i in range(len(l))]
	ans[0] = l[0]
	for i in range(1, k):
		ans[i] = l[i] + ans[i - 1]
	for i in range(k - 1, len(ans)):
		ans[i] = l[i] + ans[i - k]
	ans[k - 1] = l[k - 1]
	f = 0
	for i in range(len(ans) - 1, -1, -1):
		if ans[i] <= p:
			f = 1
			print(i + 1)
			break
	if f == 0:
		print(0)


def f(x, k):
	return x // k * k + (1 if x % k > 0 else 0)
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	s = [0] * n
	s[0] = a[0]
	for i in range(1, k - 1):
		s[i] = s[i - 1] + a[i]
	for i in range(k - 1, n):
		s[i] = min(a[i] + s[i - k], a[i] + s[i - 1])
	y = 0
	for x in range(n):
		if s[x] <= p:
			y = x + 1
	print(y)


import sys
import bisect
import heapq
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
for _ in range(int(ri())):
	(n, p, k) = Ri()
	a = Ri()
	a.sort()
	prefix = [0] * (n + 1)
	for i in range(0, len(a)):
		prefix[i + 1] = a[i] + prefix[i]
	dpc = [i for i in a]
	dpc = [0] + dpc
	dpn = [0] * n
	for i in range(len(a)):
		if i < k - 1:
			if a[i] <= p and dpc[i] <= p - a[i]:
				dpc[i + 1] = a[i] + dpc[i]
				dpn[i] = i + 1
			else:
				dpc[i + 1] = INF
				dpn[i] = 0
			continue
		if a[i] <= p and dpc[i + 1 - k] <= p - a[i]:
			dpc[i + 1] = a[i] + dpc[i - k + 1]
			dpn[i] = i + 1
		else:
			dpc[i + 1] = INF
			dpn[i] = 0
	print(max(dpn))


import os, sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(n, p, k) = map(int, input().split())
		a = sorted(map(int, input().split()))
		ans = 0
		su = 0
		for i in range(k - 1):
			p1 = p - su
			for j in range(i, n, k):
				p1 -= a[j]
				if p1 <= 0:
					break
			su += a[i]
			if p1 >= 0:
				ans = max(ans, j + 1)
			else:
				ans = max(ans, j - k + 1)
		p1 = p
		for j in range(k - 1, n, k):
			p1 -= a[j]
			if p1 <= 0:
				break
		if p1 >= 0:
			ans = max(ans, j + 1)
		else:
			ans = max(ans, j - k + 1)
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
pr = lambda x: x

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	for _ in range(int(input())):
		(n, p, k) = aj()
		A = sorted(aj())
		S = [0] * (n + k + 5)
		for i in range(k - 1):
			S[i] = A[i] + S[i - 1]
		for i in range(k - 1, n):
			S[i] = S[i - k] + A[i]
		ans = -1
		for i in range(n):
			if S[i] <= p:
				ans = i
		print(ans + 1)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	from aj import *
except:
	pass
solve()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	dp = [10 ** 18] * (n + 1)
	dp[0] = 0
	for i in range(1, n + 1):
		dp[i] = dp[i - 1] + a[i - 1]
		if i - k >= 0:
			dp[i] = min(dp[i], dp[i - k] + a[i - 1])
	for i in range(n, -1, -1):
		if dp[i] <= p:
			print(i)
			break


import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	(n, p, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	aSum = [0 for _ in range(n)]
	dp = [0 for _ in range(n)]
	ans = 0
	for i in range(n):
		dp[i] += a[i]
		if 1 <= i < k - 1:
			dp[i] += dp[i - 1]
		if i - k >= 0:
			dp[i] += dp[i - k]
		if dp[i] <= p:
			ans = max(ans, i + 1)
	print(ans)


import os
import sys
from io import BytesIO, IOBase
from itertools import accumulate
from bisect import bisect

def solution(arr, n, p, k):
	arr.sort()
	prices = [0] * (n + 1)
	res = 0
	for i in range(k - 1):
		prices[i] = prices[i - 1] + arr[i]
		if prices[i] <= p:
			res = i + 1
	for i in range(k - 1, n):
		prices[i] = prices[i - k] + arr[i]
		if prices[i] <= p:
			res = i + 1
	write(res)

def main():
	for _ in range(r_int()):
		(n, p, k) = r_array()
		arr = r_array()
		solution(arr, n, p, k)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def write(*args, end='\n'):
	for x in args:
		sys.stdout.write(str(x) + ' ')
	sys.stdout.write(end)

def r_array():
	return [int(x) for x in input().split()]

def r_int():
	return int(input())
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	for i in range(1, k - 1):
		a[i] += a[i - 1]
	for i in range(k, n):
		a[i] += a[i - k]
	ans = -1
	for i in range(n):
		if a[i] <= p:
			ans = i
	print(ans + 1)


t = int(input())
dp = []
for i in range(t):
	(n, p, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	dp = [0 for j in range(n + 1)]
	for j in range(1, len(l) + 1):
		if j < k:
			dp[j] = dp[j - 1] + l[j - 1]
		else:
			dp[j] = dp[j - k] + l[j - 1]
	for j in range(n + 1):
		if dp[j] <= p:
			ans = j
	print(ans)


import sys

def ints():
	return map(int, sys.stdin.readline().split())
for _ in range(int(input())):
	(n, p, k) = ints()
	A = list(sorted(ints()))
	dp = [0] * k
	dp[0] = 0
	r = 0
	for i in range(1, k):
		dp[i] = A[i - 1] + dp[i - 1]
		if dp[i] <= p:
			r = i
	for i in range(k):
		s = dp[i]
		j = i + k
		while j <= n and s + A[j - 1] <= p:
			r = max(j, r)
			s += A[j - 1]
			j = j + k
	print(r)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = list(sorted(map(int, input().split())))
	s = 0
	maxx = 0
	for i in range(0, k + 1):
		cnt = 0
		summ = 0
		if i != k and summ + s + a[i] <= p:
			s += a[i]
			summ += s
			cnt += i + 1
			j = i + k
			while j < n and summ + a[j] <= p:
				summ += a[j]
				cnt += k
				j += k
		elif i == k:
			j = k - 1
			while j < n and summ + a[j] <= p:
				summ += a[j]
				cnt += k
				j += k
		if cnt > maxx:
			maxx = cnt
	print(maxx)


from itertools import *
from sys import *

def dynamic(a, n, k, p):
	dp = []
	ans = 0
	for i in range(0, n):
		if i == 0:
			dp.append(a[i])
		elif i < k - 1:
			dp.append(a[i] + dp[i - 1])
		elif i == k - 1:
			dp.append(a[i])
		else:
			dp.append(a[i] + dp[i - k])
		if dp[i] <= p:
			ans = i + 1
	return ans
t = int(stdin.readline())
for _ in range(t):
	(n, p, k) = map(int, stdin.readline().split())
	a = [int(x) for x in stdin.readline().split()]
	a.sort()
	print(dynamic(a, n, k, p))


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	dp = [float('inf')] * (n + 1)
	dp[0] = 0
	ans = 0
	for i in range(n):
		dp[i + 1] = min(dp[i + 1], dp[i] + arr[i])
		if i >= k - 1:
			dp[i + 1] = min(dp[i + 1], arr[i] + dp[i - k + 1])
		if dp[i + 1] <= p:
			ans = i + 1
	print(ans)


import sys

def ints():
	return map(int, sys.stdin.readline().split())
for _ in range(int(input())):
	(n, p, k) = ints()
	A = list(sorted(ints()))
	dp = [0] * k
	r = 0
	for i in range(1, n + 1):
		imk = i % k
		dp[imk] = A[i - 1] + dp[(i - 1) % k] if i < k else A[i - 1] + dp[imk]
		if dp[imk] <= p:
			r = i
	print(r)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 0
	count = 0
	without_offer = 0
	for i in range(k):
		sum = without_offer
		if sum > p:
			break
		count = i
		for j in range(i + k - 1, n, k):
			if sum + arr[j] <= p:
				count += k
				sum += arr[j]
			else:
				break
		without_offer += arr[i]
		ans = max(ans, count)
	print(ans)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	l = [0] * n
	l[0] = arr[0]
	for i in range(1, k - 1):
		l[i] = l[i - 1] + arr[i]
	l[k - 1] = arr[k - 1]
	for i in range(k, n):
		l[i] = l[i - k] + arr[i]
	ans = 0
	for i in range(n):
		if l[i] <= p:
			ans = i + 1
	print(ans)


import math
import bisect
from collections import defaultdict
from collections import OrderedDict
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	x = 0
	pre_sum = [0] * n
	for i in range(n):
		if i < k - 1:
			pre_sum[i] = pre_sum[i - 1] + a[i]
		else:
			pre_sum[i] = pre_sum[i - k] + a[i]
	for i in range(n):
		if pre_sum[i] <= p:
			x = i + 1
	print(x)


for _ in range(int(input())):
	(n, p, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	pref = [0]
	for i in a[:k - 1]:
		pref.append(pref[-1] + i)
	ans = 0
	for (i, num) in enumerate(pref):
		cur_ans = 0
		_p = p
		if _p >= num:
			_p -= num
			cur_ans += i
		else:
			break
		for j in range(i + k - 1, n, k):
			if _p >= a[j]:
				cur_ans += k
				_p -= a[j]
			else:
				break
		ans = max(ans, cur_ans)
	print(ans)


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import permutations
from copy import deepcopy
from heapq import *

def lcm(a, b):
	return a * b // gcd(a, b)

def fact(n, mo):
	f = [1]
	for i in range(1, n + 1):
		f.append(f[-1] * i % mo)
	invf = [0] * (n + 1)
	invf = pow(f[-1], mo - 2, mo)
	for i in range(n - 1, -1, -1):
		invf[i] = (i + 1) * invf[i + 1] % mo
	return (f, invf)

def mod(a, m):
	if a > m:
		return a % m
	return a

def main():
	for t in range(int(input())):
		(n, p, k) = map(int, input().split())
		a = sorted(list(map(int, input().split())))
		dp = [0 for i in range(n + 1)]
		c = [0]
		for i in range(n):
			c.append(c[-1] + a[i])
		for i in range(1, k):
			dp[i] = c[i]
		for i in range(k, n + 1):
			dp[i] = min(c[i], dp[i - k] + a[i - 1])
		ma = 0
		for i in range(1, n + 1):
			if dp[i] <= p:
				ma = max(ma, i)
		print(ma)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import defaultdict as dd
import math
import sys

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))

def solve(n, p, k, dat):
	pp = p
	dat.sort()
	idx = k - 1
	while idx < len(dat) and p >= dat[idx]:
		p -= dat[idx]
		idx += k
	idx -= k - 1
	if idx == 0:
		while p >= dat[idx]:
			p -= dat[idx]
			idx += 1
		return idx
	off = 0
	while True:
		if idx + off > len(dat):
			break
		curr = sum(dat[:off]) + sum(dat[off:idx + off + 1:k])
		if curr > pp:
			break
		off += 1
	return min(len(dat), idx + off)

def helper():
	(n, p, k) = mi()
	dat = lm()
	print(solve(n, p, k, dat))
T = nn()
for _ in range(T):
	helper()


import sys
input = sys.stdin.readline

def inp():
	return int(input().rstrip())

def inlt():
	return list(map(int, input().rstrip().split()))

def insr():
	s = input().rstrip()
	return s[:len(s) - 1]

def invr():
	return map(int, input().rstrip().split())
t = inp()
for _ in range(t):
	(n, p, k) = invr()
	nums = inlt()
	nums.sort()
	dp = [-1 for i in range(n + 1)]
	dp[0] = p
	ans = 0
	for i in range(1, n + 1):
		if i >= k:
			dp[i] = max(dp[i - k] - nums[i - 1], dp[i - 1] - nums[i - 1])
		else:
			dp[i] = dp[i - 1] - nums[i - 1]
		if dp[i] >= 0:
			ans = i
	print(ans)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	leftMoney = [0 for i in range(n)]
	dp = [0 for i in range(n)]
	leftMoney[0] = p
	for i in range(n):
		if i >= k - 1:
			if leftMoney[i] >= a[i]:
				dp[i] = dp[i - 1] + 1
				if i + 1 < n:
					leftMoney[i + 1] = leftMoney[i] - a[i]
			else:
				dp[i] = dp[i - 1]
				if i + 1 < n:
					leftMoney[i + 1] = leftMoney[i]
			if leftMoney[i - k + 1] >= a[i]:
				dp[i] = max(dp[i], k + (dp[i - k] if i >= k else 0))
				if i + 1 < n:
					leftMoney[i + 1] = leftMoney[i - k + 1] - a[i]
		elif leftMoney[i] >= a[i]:
			dp[i] = dp[i - 1] + 1
			if i + 1 < n:
				leftMoney[i + 1] = leftMoney[i] - a[i]
		else:
			dp[i] = dp[i - 1]
			if i + 1 < n:
				leftMoney[i + 1] = leftMoney[i]
	print(dp[n - 1])


from sys import stdin

def input():
	return stdin.readline()[:-1]

def intput():
	return int(input())

def sinput():
	return input().split()

def intsput():
	return map(int, sinput())
t = intput()
for _ in range(t):
	(n, p, k) = intsput()
	a = list(intsput())
	a.sort()
	end = n - 1
	start = 0
	middle = (end + start + 1) // 2
	if middle + k - (middle + 1) % k <= end:
		middle = middle + k - (middle + 1) % k
	while end != start:
		s = 0
		parity = 0
		for i in range(middle, -1, -1):
			if parity % k and i - (k - parity) + 1 >= 0:
				pass
			else:
				s += a[i]
			parity += 1
			parity %= k
		if s <= p:
			start = middle
		else:
			end = middle - 1
		middle = (end + start + 1) // 2
		if middle + k - (middle + 1) % k <= end:
			middle = middle + k - (middle + 1) % k
	if end == 0:
		if a[0] > p:
			print(0)
			continue
	print(end + 1)


from os import path
import sys, time
mod = int(1000000000.0 + 7)
from math import ceil, floor, gcd, log, log2, factorial, sqrt
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, permutations
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
I = lambda : int(sys.stdin.buffer.readline())
lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda : sys.stdin.readline().strip('\n')
grid = lambda r: [lint() for i in range(r)]
localsys = 0
start_time = time.time()
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)

def ceill(n, x):
	return (n + x - 1) // x
T = 1

def solve():
	(n, p, k) = lint()
	a = lint()
	a.sort()
	(ans, pre) = (0, 0)
	for i in range(k):
		s = pre
		cnt = i
		if pre > p:
			break
		for j in range(i + k - 1, n, k):
			if s + a[j] <= p:
				s += a[j]
				cnt += k
			else:
				break
		ans = max(ans, cnt)
		pre += a[i]
	print(ans)

def run():
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
run()
T = I() if T else 1
for _ in range(T):
	solve()
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


T = int(input())
INF = float('inf')
for _ in range(T):
	(N, P, K) = map(int, input().split())
	arr = sorted([int(x) for x in input().split()])
	dp = [None] * N
	if arr[0] > P:
		print(0)
		continue
	else:
		dp[0] = P - arr[0]
	for i in range(1, N):
		a = dp[i - 1]
		b = dp[i - K] if i - K >= 0 else P if i - K == -1 else -INF
		dp[i] = max(a, b) - arr[i]
	best = 0
	for (i, x) in enumerate(dp):
		if x >= 0:
			best = i
	print(best + 1)


t = int(input())
for o in range(t):
	(n, p, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	a.sort()
	maxBundles = 1
	c = p
	ans = 0
	while 1:
		if maxBundles * k - 1 < len(a):
			c -= a[maxBundles * k - 1]
		else:
			maxBundles -= 1
			break
		if c < 0:
			maxBundles -= 1
			break
		maxBundles += 1
	initPrice = 0
	for i in range(k):
		c = p
		curBundles = 1
		initPrice += a[i]
		c -= initPrice
		if c < 0 and maxBundles == 0:
			ans = i
			break
		while 1:
			if curBundles * k + i < len(a):
				c -= a[curBundles * k + i]
			else:
				curBundles -= 1
				break
			if c < 0:
				curBundles -= 1
				break
			curBundles += 1
		if curBundles < maxBundles:
			ans = maxBundles * k + i
			break
	print(ans)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def solve():
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	s = 0
	ans = 0
	for i in range(k):
		if i:
			s += a[i - 1]
		tmp = s
		ans_tmp = i
		if tmp <= p:
			ans = max(ans, ans_tmp)
		for j in range(k - 1 + i, n, k):
			tmp += a[j]
			ans_tmp += k
			if tmp <= p:
				ans = max(ans, ans_tmp)
			else:
				break
	print(ans)
t = int(input())
for i in range(t):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	ar.sort()
	li = [0]
	for i in range(k - 1):
		li.append(li[-1] + ar[i])
	for i in range(k - 1, n):
		li.append(li[i - k + 1] + ar[i])
	ans = 0
	for i in range(1, n + 1):
		if li[i] <= p:
			ans = i
	print(ans)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	dp = [10 ** 10 for i in range(n + 1)]
	dp[0] = 0
	for i in range(1, n + 1):
		dp[i] = min(dp[i], dp[i - 1] + a[i - 1])
		if i >= k:
			dp[i] = min(dp[i], dp[i - k] + a[i - 1])
	ans = 0
	for i in range(n + 1):
		if dp[i] <= p:
			ans = i
	print(ans)


t = int(input())
for i in range(t):
	ch = input()
	L = [int(i) for i in ch.split()]
	n = L[0]
	p = L[1]
	k = L[2]
	ch = input()
	L = [int(i) for i in ch.split()]
	L.sort()
	L2 = [0] * n
	L2[0] = L[0]
	for i in range(1, k - 1):
		L2[i] = L2[i - 1] + L[i]
	L2[k - 1] = L[k - 1]
	if k < n:
		for i in range(k, n):
			L2[i] = L2[i - k] + L[i]
	test = False
	for i in range(n):
		if L2[n - i - 1] <= p:
			print(n - i)
			test = True
			break
	if test == False:
		print(0)


import sys
input = lambda : sys.stdin.readline()
for i in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		if i < k:
			dp[i] = dp[i - 1] + a[i - 1]
		else:
			dp[i] = min(dp[i - 1], dp[i - k]) + a[i - 1]
	ans = 0
	for j in range(n + 1):
		if dp[j] <= p:
			ans = j
	print(ans)


t = int(input())
import sys
input = sys.stdin.readline
while t > 0:
	t -= 1
	(n, p, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	dp = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		if i - k >= 0:
			dp[i] = a[i - 1] + dp[i - k]
		else:
			dp[i] = dp[i - 1] + a[i - 1]
	flag = 0
	z = 0
	for i in range(1, n + 1):
		if dp[i] > p:
			pass
		else:
			z = i
	print(z)


import bisect
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	p = int(l[1])
	k = int(l[2])
	l = input().split()
	li = [int(i) for i in l]
	li.sort()
	sumfi = [[] for i in range(k)]
	sumi1 = 0
	sumi2 = 0
	sumxi = []
	sumx = 0
	for i in range(n):
		sumx += li[i]
		sumxi.append(sumx)
	for i in range(n):
		x = (i + 1) % k
		if sumfi[x] == [] and x != 0:
			sumfi[x].append(sumxi[i])
		elif sumfi[x] == [] and x == 0:
			sumfi[x].append(li[i])
		else:
			sumfi[x].append(sumfi[x][-1] + li[i])
	lfi = []
	for i in range(k):
		if i != 0:
			lfi.append(k * bisect.bisect(sumfi[i], p) - (k - i))
		else:
			lfi.append(k * bisect.bisect(sumfi[i], p))
	print(max(lfi))


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = [int(o) for o in input().split()]
	p1 = p
	taken = [0] * n
	a = sorted(a)
	dp = [0] * (n + 1)
	a.append(0)
	lol = 0
	for i in range(n):
		dp[i] = a[i] + dp[i - 1]
	cost = dp[:]
	for i in range(k - 1, n):
		cost[i] = cost[i - k] + a[i]
	i = n - 1
	while cost[i] > p:
		i -= 1
	lol = i + 1
	print(lol)


T = int(input())
for t in range(1, T + 1):
	(n, p, k) = map(int, input().split())
	values = sorted(list(map(int, input().split())))
	cumsum = [0]
	for i in range(k - 1):
		cumsum.append(cumsum[-1] + values[i])
	best = 0
	for i in range(k):
		ith_best = 0
		mysum = cumsum[i]
		if mysum > p:
			best = max(best, ith_best)
			break
		else:
			ith_best = i
			best = max(best, ith_best)
		for j in range(i + k - 1, n, k):
			mysum += values[j]
			if mysum > p:
				break
			else:
				ith_best += k
				best = max(best, ith_best)
	print(best)


from collections import defaultdict, Counter
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

def read():
	return list(map(int, input().strip().split()))

def readf():
	return list(map(int, file.readline().strip().split()))
ans_ = []

def solve():
	for _ in range(nin()):
		(n, p, k) = read()
		arr = read()
		arr.sort()
		pref = [0] * n
		pref[0] = arr[0]
		ans = 0
		for i in range(n):
			pref[i] = pref[i - 1 if i < k - 1 else i - k] + arr[i]
			if pref[i] <= p:
				ans = i + 1
		print(ans)
solve()
for i in ans_:
	print(i)


from collections import deque
import sys
import math
input = sys.stdin.buffer.readline
q = int(input())
for _ in range(q):
	(n, p, k) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort()
	s = 0
	lss = []
	for i in range(k):
		if s <= p:
			lss.append([s, i])
		else:
			lss.append([10 ** 10, 0])
		s += x[i]
	i = 0
	ok = True
	while ok:
		i += 1
		for z in range(k):
			if z + i * k - 1 < n:
				if lss[z][0] + x[z + i * k - 1] <= p:
					lss[z][0] += x[z + i * k - 1]
					lss[z][1] += k
			else:
				ok = False
				break
	mmm = 0
	for xx in lss:
		if xx[1] > mmm:
			mmm = xx[1]
	print(mmm)


import sys
t = int(input())
ans = [0] * t
for pi in range(t):
	(n, p, k) = map(int, sys.stdin.readline().split())
	a = [0] + sorted(map(int, sys.stdin.readline().split()))
	for i in range(1, k):
		a[i] += a[i - 1]
	for i in range(1, n - k + 1):
		a[i + k] += a[i]
	for i in range(n + 1):
		if a[i] <= p:
			ans[pi] = i
print(*ans, sep='\n')


t = int(input())
while t > 0:
	t -= 1
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	goods = 0
	pref = [0] * n
	for i in range(n):
		if i < k - 1:
			pref[i] = a[i]
			if i:
				pref[i] += pref[i - 1]
		else:
			pref[i] = a[i]
			if i >= k:
				pref[i] += pref[i - k]
		if pref[i] <= p:
			goods = max(goods, i + 1)
	print(goods)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	h = sorted(list(map(int, input().split())))
	g = []
	for i in h:
		if i <= p:
			g.append(i)
	if k == len(g):
		print(len(g))
		continue
	if p < 1000000000.0:
		r = 0
		ass = 0
		assi = n % k
		su = sum(g[k - 1:r:k])
		while su <= p and r <= len(g):
			r += 100
			su = sum(g[k - 1:r:k])
		while su > p or r > len(g):
			r -= 1
			su = sum(g[k - 1:r:k])
	else:
		r = len(g)
		su = 0
		ass = 0
		assi = n % k
		su = sum(g[k - 1:r:k])
		while su > p:
			r -= 1
			su = sum(g[k - 1:r:k])
	if not g:
		print(0)
		continue
	saas = [0, g[0]]
	for i in range(1, len(g)):
		saas.append(g[i] + saas[i])
	for i in range(k):
		if i > len(saas) - 1:
			break
		su = saas[i] + sum(g[i + k - 1:r:k])
		if su <= p:
			ass = max(ass, i + (r - i) // k * k)
	print(ass)


for i in range(int(input())):
	(n, p, k) = map(int, input().split())
	l = sorted(map(int, input().split()))
	dp = [0 for j in range(n + 1)]
	for j in range(1, n + 1):
		if j < k:
			dp[j] = dp[j - 1] + l[j - 1]
		else:
			dp[j] = dp[j - k] + l[j - 1]
	for j in range(n + 1):
		if dp[j] <= p:
			ans = j
	print(ans)


t = int(input())
for i in range(t):
	(n, p, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l1 = []
	c = 0
	for i in range(n):
		if i < k - 1:
			c += l[i]
			l1.append(c)
		elif i == k - 1:
			l1.append(l[i])
		else:
			l1.append(l[i] + l1[i - k])
	ans = 0
	for i in range(n - 1, -1, -1):
		if l1[i] <= p:
			ans = i + 1
			break
	print(ans)


t = int(input())
for test in range(t):
	(n, p, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	carr = [0 for i in range(n + 5)]
	carr[0] = arr[0]
	for i in range(1, k - 1):
		carr[i] = carr[i - 1] + arr[i]
	carr[k - 1] = arr[k - 1]
	for i in range(k, n):
		carr[i] = carr[i - k] + arr[i]
	count = 0
	for i in range(n):
		if carr[i] <= p:
			count = i + 1
	print(count)


t = int(input())
for i in range(t):
	s = list(map(int, input().split()))
	n = s[0]
	p = s[1]
	k = s[2]
	a = list(map(int, input().split()))
	a.sort()
	r = [0] * k
	s = [0] * k
	ps = 0
	for i in range(1, k):
		ps += a[i - 1]
		if s[i] + ps <= p:
			r[i] += i
			s[i] += ps
	for i in range(k):
		for j in range(k + i, n + 1, k):
			if k + i > n:
				break
			elif a[j - 1] + s[i] <= p:
				r[i] += k
				s[i] += a[j - 1]
			else:
				break
	print(max(r))


t = int(input())
while t != 0:
	(n, p, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	list1.sort()
	cost = [0] * (n + 1)
	for i in range(1, n + 1):
		if i < k:
			cost[i] = cost[i - 1] + list1[i - 1]
		else:
			cost[i] = cost[i - k] + list1[i - 1]
	ans = 0
	for i in range(n + 1):
		if cost[i] <= p:
			ans = i
	print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	(r, re) = (0, 0)
	if p < l[0]:
		print(0)
	else:
		pe = p
		g = p
		c = 0
		for i in range(k - 1, n, k):
			if pe >= l[i]:
				re += k
				pe -= l[i]
			else:
				break
		for j in range(k - 1):
			if g - l[j] < 0:
				break
			else:
				r = j + 1
				g -= l[j]
				p = g
				for i in range(k + j, n, k):
					if p >= l[i]:
						r += k
						p -= l[i]
					else:
						break
				if r > c:
					c = r
		print(max(re, c))


t = int(input())
for _ in range(t):
	(n, p, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort()
	t = [0] * len(l)
	c = [0] * len(l)
	for i in range(n):
		if i < k:
			if i == 0:
				if p >= l[i]:
					t[i] = 1
					c[i] = p - l[i]
			elif i > 0 and i < k - 1:
				if c[i - 1] >= l[i]:
					t[i] = t[i - 1] + 1
					c[i] = c[i - 1] - l[i]
				else:
					t[i] = t[i - 1]
					c[i] = c[i - 1]
			elif i == k - 1:
				if p >= l[i]:
					t[i] = k
					c[i] = p - l[i]
		elif c[i - k] >= l[i]:
			c[i] = c[i - k] - l[i]
			t[i] = t[i - k] + k
		else:
			c[i] = c[i - 1]
			t[i] = t[i - 1]
	print(max(t))


from itertools import accumulate

def solve():
	(n, price, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr[:0] = [0]
	arr.sort()
	dp = [[0, 0] for i in range(n + 1)]
	for i in range(1, n + 1):
		if i >= k:
			p1 = arr[i]
			g1 = k
			p2 = dp[i - k][0] + arr[i]
			g2 = dp[i - k][1] + k
			if p2 <= price:
				dp[i] = [p2, g2]
			elif p1 <= price:
				dp[i] = [p1, g1]
			else:
				dp[i] = dp[i - 1]
		elif dp[i - 1][0] + arr[i] <= price:
			dp[i][0] = dp[i - 1][0] + arr[i]
			dp[i][1] = dp[i - 1][1] + 1
		else:
			dp[i] = dp[i - 1]
	maxi = max([dp[i][1] for i in range(1, n + 1)])
	print(maxi)
t = int(input())
while t > 0:
	solve()
	t -= 1


def check(costs, k, bought):
	res = 0
	while bought > 0:
		res += costs[bought - 1]
		if bought >= k:
			bought -= k
		else:
			bought -= 1
	return res
t = int(input())
for _ in range(t):
	(n, p, k) = list(map(int, input().split(' ')))
	costs = sorted(list(map(int, input().split(' '))))
	ans = 0
	mon_req = [0] * (n + 1)
	for i in range(1, n + 1):
		if i >= k:
			mon_req[i] = mon_req[i - k] + costs[i - 1]
		else:
			mon_req[i] = mon_req[i - 1] + costs[i - 1]
	for (i, mon) in enumerate(mon_req):
		if mon <= p:
			ans = i
	print(ans)


for t in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = [0] + sorted(list(map(int, input().split())))
	dp = [-1 for i in range(n + 1)]
	dp[0] = p
	for i in range(1, n + 1):
		if i - k < 0:
			dp[i] = max(dp[i], dp[i - 1] - a[i])
		else:
			dp[i] = max(dp[i], dp[max(0, i - k)] - a[i])
	maxi = 0
	for i in range(n + 1):
		if dp[i] >= 0:
			maxi = i
	print(maxi)


for _ in range(int(input())):
	(n, p, k) = map(int, input().strip().split())
	A = list(sorted([int(x) for x in input().strip().split()]))
	dp = [0] * k
	dp[0] = 0
	r = 0
	for i in range(1, k):
		dp[i] = A[i - 1] + dp[i - 1]
		if dp[i] <= p:
			r = i
	for i in range(k):
		s = dp[i]
		j = i + k
		while j <= n and s + A[j - 1] <= p:
			r = max(j, r)
			s += A[j - 1]
			j = j + k
	print(r)


def idp(a, dp, i, k):
	if i - k >= 0:
		return min(a[i] + dp[i - 1], a[i] + dp[i - k])
	else:
		return a[i] + dp[i - 1]
t = int(input())
for tc in range(t):
	(n, p, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	dp = [0] * n
	dp[0] = a[0]
	for i in range(0, k - 1):
		dp[i] = a[i] + dp[i - 1]
	dp[k - 1] = a[k - 1]
	for i in range(k, n):
		dp[i] = idp(a, dp, i, k)
	bst = 0
	for i in range(n):
		if dp[i] <= p:
			bst = i + 1
	print(bst)


T = int(input())

def solve():
	[N, P, K] = list(map(int, input().split()))
	A = list(map(int, input().split()))
	A = sorted(A)
	dp = [float('inf') for _ in range(N)]
	ans = 0
	for i in range(N):
		if i < K - 1:
			if i == 0:
				dp[i] = A[i]
				continue
			dp[i] = A[i] + dp[i - 1]
			continue
		if i == K - 1:
			dp[i] = A[i]
			continue
		dp[i] = A[i] + dp[i - K]
	for ii in range(len(dp)):
		if dp[ii] <= P:
			ans = ii + 1
	return ans
for _ in range(T):
	print(solve())


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
for _ in range(inp()):
	(n, p, k) = inpl()
	a = inpl()
	a.sort()
	aa = list(itertools.accumulate(a))
	aa[k - 1] = a[k - 1]
	for j in range(k):
		now = 0
		for (ind, i) in enumerate(range(j, n)[::k]):
			if ind == 0:
				now = aa[i]
				continue
			now += a[i]
			aa[i] = now
	res = 0
	for i in range(n):
		if p >= aa[i]:
			res = i + 1
	print(res)


for h in range(int(input())):
	(n, p, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	a.sort()
	a.insert(0, 0)
	price = p
	maxi = 0
	for i in range(k):
		if a[i] <= price:
			p -= a[i]
			price = p
			j = i + k
			goods = i
			while j < n + 1:
				if a[j] <= price:
					goods += k
					price -= a[j]
				j += k
			maxi = max(maxi, goods)
	print(maxi)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	dp = [0] * (n + 10)
	ans = 0
	for i in range(k - 1):
		dp[i] = l[i] + dp[i - 1]
		if dp[i] <= p:
			ans = i + 1
	for i in range(k - 1, n):
		dp[i] = l[i] + dp[i - k]
		if dp[i] <= p:
			ans = i + 1
	print(ans)


for j in range(int(input())):
	(n, p, k) = [int(x) for x in input().split()]
	goods = [int(x) for x in input().split()]
	goods.sort()
	dp = [0] * n
	dp[0] = goods[0]
	if dp[0] > p:
		print(0)
		continue
	for i in range(1, k - 1):
		dp[i] = goods[i] + dp[i - 1]
	for i in range(k - 1, n):
		dp[i] = goods[i] + min(dp[i - 1], dp[i - k])
	res = 0
	for i in range(0, n):
		if dp[i] <= p:
			res = i + 1
	print(res)


from collections import deque
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	pre = [0]
	for i in range(n):
		pre.append(pre[i] + a[i])
	lo = 0
	ans = 0
	while lo <= min(k, n):
		mon = p
		mid = lo
		curr = mid
		if pre[mid] > mon:
			lo += 1
			continue
		mon -= pre[mid]
		r = mid + k - 1
		stack = deque()
		while r < n:
			if a[r] > mon:
				break
			curr += k
			mon -= a[r]
			r += k
		ans = max(ans, curr)
		lo += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	sum = [0]
	for i in range(k - 1):
		sum.append(sum[-1] + l[i])
	for i in range(k - 1, len(l)):
		sum.append(l[i] + sum[i - k + 1])
	ans = 0
	for i in range(n + 1):
		if sum[i] <= p:
			ans = i
	print(ans)


t = int(input())
for ii in range(t):
	(n, p, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a = sorted(a)
	a = [None] + a
	s = [0] * (n + 1)
	last_ind = 0
	for i in range(1, n + 1):
		if i < k:
			s[i] = a[i] + s[i - 1]
		else:
			s[i] = a[i] + s[i - k]
		if s[i] <= p:
			last_ind = i
	print(last_ind)


T = int(input())
for _ in range(T):
	(n, p, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li.sort()
	pref = 0
	ans = 0
	sum = 0
	for i in range(k):
		sum = pref
		if sum > p:
			break
		cnt = i
		for j in range(i + k - 1, n, k):
			if sum + li[j] <= p:
				cnt += k
				sum += li[j]
			else:
				break
		pref += li[i]
		ans = max(cnt, ans)
	print(ans)


import sys

def debug(*args):
	print(*args, file=sys.stderr)
t = int(input())
for _ in range(t):
	(n, p, k) = list(map(int, input().split()))
	ai = list(map(int, input().split()))
	ai.sort()
	ai_accum = len(ai) * [0]
	for i in range(len(ai)):
		ai_accum[i] = ai_accum[i - 1] + ai[i] if i > 0 else ai[i]
	ans = 0
	for i in range(min(k, n)):
		if i > 0 and ai_accum[i - 1] > p:
			break
		temp_ans = i
		temp_p = p - ai_accum[i - 1] if i > 0 else p
		for j in range(i + k - 1, n, k):
			if ai[j] > temp_p:
				break
			temp_p -= ai[j]
			temp_ans += k
		ans = max(ans, temp_ans)
	print(ans)


tt = int(input())
for kase in range(tt):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	dp = [0] * n
	for i in range(n):
		if i >= k - 1:
			dp[i] = a[i] + (dp[i - k] if i - k >= 0 else 0)
		else:
			dp[i] = a[i] + (dp[i - 1] if i > 0 else 0)
	cnt = 0
	for i in range(n):
		if dp[i] <= p:
			cnt = i + 1
	print(cnt)