Businessman Divan loves chocolate! Today he came to a store to buy some chocolate. Like all businessmen, Divan knows the value of money, so he will not buy too expensive chocolate. At the same time, too cheap chocolate tastes bad, so he will not buy it as well.

The store he came to has $n$ different chocolate bars, and the price of the $i$-th chocolate bar is $a_i$ dollars. Divan considers a chocolate bar too expensive if it costs strictly more than $r$ dollars. Similarly, he considers a bar of chocolate to be too cheap if it costs strictly less than $l$ dollars. Divan will not buy too cheap or too expensive bars.

Divan is not going to spend all his money on chocolate bars, so he will spend at most $k$ dollars on chocolates.

Please determine the maximum number of chocolate bars Divan can buy.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The description of each test case consists of two lines. The first line contains integers $n$, $l$, $r$, $k$ ($1 \le n \le 100$, $1 \le l \le r \le 10^9$, $1 \le k \le 10^9$) — the lowest acceptable price of a chocolate, the highest acceptable price of a chocolate and Divan's total budget, respectively.

The second line contains a sequence $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) integers — the prices of chocolate bars in the store.


-----Output-----

For each test case print a single integer — the maximum number of chocolate bars Divan can buy.


-----Examples-----

Input
8
3 1 100 100
50 100 50
6 3 5 10
1 2 3 4 5 6
6 3 5 21
1 2 3 4 5 6
10 50 69 100
20 30 40 77 1 1 12 4 70 10000
3 50 80 30
20 60 70
10 2 7 100
2 2 2 2 2 7 7 7 7 7
4 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
1 1 1 1
1
Output
2
2
3
0
0
10
1
1


-----Note-----

In the first example Divan can buy chocolate bars $1$ and $3$ and spend $100$ dollars on them.

In the second example Divan can buy chocolate bars $3$ and $4$ and spend $7$ dollars on them.

In the third example Divan can buy chocolate bars $3$, $4$, and $5$ for $12$ dollars.

In the fourth example Divan cannot buy any chocolate bar because each of them is either too cheap or too expensive.

In the fifth example Divan cannot buy any chocolate bar because he considers the first bar too cheap, and has no budget for the second or third.

In the sixth example Divan can buy all the chocolate bars in the shop.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Complete search

Constructive algorithms


Solutions:
for _ in range(int(input())):
	(n, l, r, k) = [int(i) for i in input().split()]
	a = sorted([int(i) for i in input().split()])
	result = 0
	c = 0
	for i in range(n):
		if a[i] >= l and r >= a[i] and (c + a[i] <= k):
			c += a[i]
			result += 1
	print(result)


a = int(input())
countl = []
for i in range(a):
	(n, l, r, k) = input().split(' ')
	(n, l, r, k) = (int(n), int(l), int(r), int(k))
	price = []
	b = input().split(' ')
	c = []
	for i in b:
		c.append(int(i))
	price = c
	count = 0
	i = 0
	price.sort()
	while k > 0:
		if l - 1 < price[i] and r + 1 > price[i]:
			k = k - price[i]
			if k > -1:
				count += 1
		i += 1
		if i == len(price):
			break
	countl.append(count)
for j in countl:
	print(j)


t = int(input())
for _ in range(t):
	(n, down, up, money) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	count = 0
	arr.sort()
	for i in range(len(arr)):
		if arr[i] >= down:
			if arr[i] <= up:
				if arr[i] <= money:
					money -= arr[i]
					count += 1
	print(count)


t = int(input())
for _ in range(t):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	res = 0
	s = 0
	for i in a:
		if l <= i <= r and s + i <= k:
			res += 1
			s += i
	print(res)


def solve():
	(n, l, r, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	count = 0
	for i in a:
		if i < l:
			continue
		elif i > r:
			break
		elif i > k:
			break
		else:
			k -= i
			count += 1
	print(count)
for i in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li.sort()
	ans = 0
	for i in range(n):
		if li[i] >= l:
			if li[i] > r:
				break
			else:
				k = k - li[i]
				if k < 0:
					break
				else:
					ans = ans + 1
	print(ans)


nC = int(input())
for loop in range(nC):
	toks = input().split()
	n = int(toks[0])
	low = int(toks[1])
	high = int(toks[2])
	maxS = int(toks[3])
	toks = input().split()
	nums = []
	for x in toks:
		nums.append(int(x))
	nums.sort()
	res = 0
	spent = 0
	for i in range(len(nums)):
		if nums[i] >= low and nums[i] <= high and (spent + nums[i] <= maxS):
			res += 1
			spent += nums[i]
	print(res)


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	s = sorted(list((int(i) for i in input().split() if int(i) >= l and int(i) <= r)))
	c = 0
	for i in s:
		if k >= i:
			c += 1
			k -= i
	print(c)


t = int(input())
for i in range(0, t):
	l1 = list(map(int, input().split()))
	n = l1[0]
	l = l1[1]
	r = l1[2]
	k = l1[3]
	l2 = list(map(int, input().split()))
	l2.sort()
	cost_sum = 0
	cho = 0
	for j in l2:
		if cost_sum <= k:
			if l <= j <= r:
				cho = cho + 1
				cost_sum = cost_sum + j
			if cost_sum <= k:
				pass
			else:
				cho = cho - 1
				break
		else:
			break
	print(cho)


for _ in range(int(input())):
	(temp, c) = (0, 0)
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	acc = []
	tot = 0
	count = 0
	for i in a:
		if i <= r and i >= l:
			acc.append(i)
	acc.sort()
	for i in acc:
		if tot + i > k:
			break
		else:
			tot += i
			count += 1
	print(count)


t = int(input())
for i in range(t):
	(n, l, r, k) = list(map(int, input().split()))
	d = list(map(int, input().split()))
	d.sort()
	cnt = 0
	v = 0
	for i in range(n):
		if d[i] >= l and d[i] <= r:
			if cnt + d[i] <= k:
				cnt += d[i]
				v += 1
		else:
			continue
	print(v)


trial = int(input())
ans = []
for i in range(trial):
	(n, l, r, k) = list(map(int, input().split()))
	price = list(map(int, input().split()))
	price_new = [x for x in price if x >= l and x <= r]
	price_new.sort()
	sum = 0
	count = 0
	if len(price_new) == 0:
		ans.append(0)
	else:
		for j in price_new:
			sum += j
			if sum > k:
				break
			else:
				count += 1
		ans.append(count)
for q in ans:
	print(q)


def main():
	t = int(input())
	for _ in range(0, t):
		(n, l, r, k) = map(int, input().split(' '))
		bars = list(map(int, input().split(' ')))
		buys = []
		length = 0
		for i in range(0, n):
			if bars[i] >= l and bars[i] <= r:
				buys.append(bars[i])
				length += 1
		buys.sort()
		total = 0
		i = 0
		printed = False
		while i < length:
			if total + buys[i] > k:
				print(i)
				printed = True
				break
			else:
				total += buys[i]
			i += 1
		if total <= k and (not printed):
			print(i)
main()


t = int(input())
while t > 0:
	t -= 1
	(n, l, r, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	count = 0
	for i in range(0, n):
		if arr[i] >= l and arr[i] <= r:
			k -= arr[i]
			count += 1
		if k < 0:
			count -= 1
			break
	print(count)


test = int(input())
for i in range(test):
	(n, l, r, k) = map(int, input().split(' '))
	temp = list(map(int, input().split(' ')))
	temp.sort()
	s = 0
	b = 0
	index = 0
	while b < k and index < len(temp):
		if l <= temp[index] <= r and (not b + temp[index] > k):
			s += 1
			b += temp[index]
		index += 1
	print(s)


for i in range(int(input())):
	(n, l, r, k) = input().split()
	(n, l, r, k) = (int(n), int(l), int(r), int(k))
	p = sorted([int(i) for i in input().split()])
	(s, c) = (0, 0)
	for i in range(n):
		if l <= p[i] <= r and s + p[i] <= k:
			s += p[i]
			c += 1
	print(c)


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	for i in range(n):
		if a[i] >= l and a[i] <= r and (k >= a[i]):
			c += 1
			k -= a[i]
	print(c)


for i in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	prices = sorted([int(x) for x in input().split()])
	num_of_chocolates = 0
	for j in range(n):
		if l <= prices[j] <= r and prices[j] <= k:
			num_of_chocolates += 1
			k -= prices[j]
	print(num_of_chocolates)


m = int(input())
s = []
answers = []
ans = 0
for i in range(m):
	(n, l, r, k) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort()
	for i2 in range(n):
		if s[i2] >= l and s[i2] <= r and (k - s[i2] >= 0):
			ans += 1
			k -= s[i2]
	answers.append(ans)
	s = []
	ans = 0
for i in range(m):
	print(answers[i])


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	a = sorted(map(int, input().split()))
	ans = 0
	for i in a:
		if k < i:
			break
		if l <= i <= r:
			k -= i
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	v = [i for i in a if i >= l and i <= r]
	v.sort()
	si = 0
	ct = 0
	if len(v) == 0 or v[0] > k:
		print('0')
	else:
		for i in range(0, len(v)):
			if si + v[i] <= k:
				si += v[i]
				ct += 1
			else:
				break
		print(ct)


t = int(input())
for i in range(t):
	l = [int(x) for x in input().split()]
	(n, m, mx, k) = (l[0], l[1], l[2], l[3])
	arr = [int(x) for x in input().split()]
	arr.sort()
	ans = 0
	for ele in arr:
		if ele <= mx and ele >= m:
			if ele > k:
				break
			else:
				ans += 1
				k -= ele
	print(ans)


T = int(input())
for _ in range(T):
	(n, l, r, k) = map(int, input().split())
	a = []
	a = list(map(int, input().split()))
	a.sort()
	cnt = 0
	for i in range(n):
		if a[i] < l:
			continue
		if a[i] > r:
			break
		if k < a[i]:
			break
		k -= a[i]
		cnt = cnt + 1
	print(cnt)


for _ in range(int(input())):
	(_, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(s, m, u, ls) = (0, min(k, r), 0, [])
	for c in a:
		if c >= l and c <= m:
			s += c
			j = len(ls) - 1
			if j < 0:
				u += 1
				ls.append([c, 1])
			else:
				i = 0
				while True:
					n = (i + j) // 2
					if ls[n][0] < c:
						i = n + 1
						if i > j:
							ls.insert(i, [c, 1])
							break
					elif ls[n][0] == c:
						ls[n][1] += 1
						break
					else:
						j = n - 1
						if i > j:
							ls.insert(i, [c, 1])
							break
				if s > k:
					q = ls[-1]
					if q[1] > 1:
						q[1] -= 1
					else:
						ls.pop()
					s -= q[0]
				else:
					u += 1
			m = min(k - s + ls[-1][0], r)
	print(u)


t = int(int(input()))
list1 = []
list2 = []
for i in range(t):
	list1.append([int(x) for x in input().split()])
	list2.append([int(x) for x in input().split()])
for i in range(t):
	list2[i].sort(reverse=False)
	n = len(list2[i])
	n1 = 0
	n2 = n
	for j in range(n):
		if list1[i][1] > list2[i][j]:
			n1 = j + 1
		elif list1[i][2] < list2[i][j]:
			n2 = j
			break
	list2[i] = list2[i][n1:n2]
	m = 0
	a = 0
	while m < list1[i][3]:
		if a == len(list2[i]):
			break
		if m + list2[i][a] > list1[i][3]:
			break
		m += list2[i][a]
		a += 1
	print(a)


t = int(input())
for tt in range(t):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for m in a:
		if m <= k and m >= l and (m <= r):
			ans += 1
			k -= m
	print(ans)


def buy_choclate(l, r, k, prices):
	prices.sort()
	count = 0
	sum = 0
	for price in prices:
		if price < l or price > r:
			continue
		elif sum + price <= k:
			sum += price
			count += 1
	return count
test_cases = int(input())
for i in range(test_cases):
	(n, l, r, k) = map(int, input().split())
	prices = list(map(int, input().split()))
	print(buy_choclate(l, r, k, prices))


number = int(input())
final = []
for i in range(number):
	input1 = input()
	input1 = input1.split()
	for i in range(0, len(input1)):
		input1[i] = int(input1[i])
	n = input1[0]
	l = input1[1]
	r = input1[2]
	k = input1[3]
	prices = input()
	prices = prices.split()
	for i in range(0, len(prices)):
		prices[i] = int(prices[i])
	x = 0
	result = 0
	prices.sort()
	for i in range(0, len(prices)):
		if prices[i] >= l and prices[i] <= r:
			x += prices[i]
			if x > k:
				break
			result += 1
	final.append(str(result))
	prices = ''
	input1 = ''
final = '\n'.join(final)
print(final)


t = int(input())
for i in range(t):
	sec = list(map(int, input().split()))
	third_line = list(map(int, input().split()))
	third_line.sort()
	filtered = list(filter(lambda x: x <= sec[2] and x >= sec[1], third_line))
	summ = sum(filtered)
	while summ > sec[3]:
		filtered.pop()
		summ = sum(filtered)
	print(len(filtered))


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls.sort()
	for i in range(len(ls)):
		if ls[i] >= l:
			a = i
			break
		elif i == len(ls) - 1:
			a = 'no'
	for j in range(1, len(ls) + 1):
		if ls[-j] <= r and j == 1:
			b = len(ls)
			break
		elif ls[-j] <= r:
			b = -j + 1
			break
		elif j == len(ls):
			b = 'no'
	cost = 0
	num = 0
	if a == 'no' or b == 'no':
		print(0)
	else:
		ls = ls[a:b]
		for i in range(len(ls)):
			if cost + ls[i] <= k:
				cost += ls[i]
				num += 1
			else:
				break
		print(num)


m = eval(input())
s = []
for i in range(m):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	a.sort()
	for j in range(n):
		if a[j] >= l and a[j] <= r:
			k -= a[j]
			if k >= 0:
				count += 1
	s.append(count)
for i in range(m):
	print(s[i])


n = int(input(''))
for i in range(n):
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	count = 0
	addive = 0
	b.sort()
	for i in range(len(b)):
		if b[i] + addive <= a[3]:
			if b[i] >= a[1] and b[i] <= a[2]:
				count += 1
				addive += b[i]
		else:
			break
	print(count)


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	Arr = list(map(int, input().split()))
	Lst = []
	for i in range(n):
		if Arr[i] >= l and Arr[i] <= r:
			Lst.append(Arr[i])
	Lst.sort()
	(Sum, Count) = (0, 0)
	for i in range(len(Lst)):
		if Sum + Lst[i] > k:
			print(Count)
			break
		else:
			Sum = Sum + Lst[i]
			Count = Count + 1
	else:
		print(Count)


t = int(input())
while t > 0:
	t = t - 1
	(n, l, r, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls = sorted(ls)
	count = 0
	for i in range(n):
		if ls[i] >= l and ls[i] <= r:
			if k > 0:
				if ls[i] <= k:
					count += 1
					k = k - ls[i]
	print(count)


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = []
	for i in a:
		if i >= l and i <= r:
			s.append(i)
	s = sorted(s)
	while sum(s) > k:
		s.pop()
	print(len(s))


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	choko = list(map(int, input().split()))
	temp = choko.copy()
	for i in temp:
		if not l <= i <= r:
			choko.remove(i)
	choko.sort()
	res = 0
	i = 0
	while k > 0 and i < len(choko) and (k >= choko[i]):
		res += 1
		k -= choko[i]
		i += 1
	print(res)


t = int(input())
for i in range(t):
	(n, l, r, k) = [int(x) for x in input().split(' ')]
	a = list(map(int, input().split(' ')))
	a.sort()
	var = 0
	COUNT = 0
	for j in range(n):
		if var >= k:
			break
		if a[j] >= l:
			if a[j] <= r:
				if var + a[j] <= k:
					var += a[j]
					COUNT += 1
	print(COUNT)


for i in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	a = sorted([*map(int, input().split())])
	f = 0
	for i in range(n):
		if a[i] >= l and a[i] <= r and (k - a[i] >= 0):
			k -= a[i]
			f += 1
	print(f)


for _ in range(int(input())):
	inp = list(map(int, input().split()))
	n = inp[0]
	l = inp[1]
	r = inp[2]
	k = inp[3]
	ch = list(filter(lambda c: l <= c <= r, map(int, input().split())))
	ch.sort()
	s = 0
	i = 0
	o = 0
	while s < k and i < len(ch):
		if s + ch[i] <= k:
			o += 1
			s += ch[i]
		i += 1
	print(o)


for _ in range(int(input())):
	(n, l, r, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	arr = filter(lambda x: x >= l, arr)
	arr = list(filter(lambda x: x <= r, arr))
	count = 0
	while len(arr) > 0:
		itr = min(arr)
		if k >= itr:
			k = k - itr
			count += 1
		else:
			break
		index = arr.index(itr)
		del arr[index]
	print(count)


t = int(input())
for i in range(t):
	(n, l, r, k) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	lis = []
	for i in range(n):
		if l <= arr[i] <= r:
			lis.append(arr[i])
	lis.sort()
	count = 0
	for j in range(len(lis)):
		if lis[j] > k:
			break
		k -= lis[j]
		count += 1
	print(count)


x = int(input(''))
s = []
for i in range(x):
	(n, l, r, k) = map(int, input('').split())
	d = list(map(int, input('').split()))
	count = 0
	h = []
	for j in d:
		if l <= j <= r:
			h.append(j)
		else:
			pass
	h.sort()
	limit = 0
	for a in h:
		limit += a
		if limit <= k:
			count += 1
		else:
			break
	s.append(count)
for g in s:
	print(g)


x = int(input())
lista = []
for i in range(x):
	a = 0
	b = 0
	y = input().split()
	z = input().split()
	z = [int(x) for x in z if int(x) >= int(y[1]) and int(x) <= int(y[2])]
	for i in sorted(z):
		if i + a <= int(y[3]):
			b += 1
			a += i
	lista.append(b)
for i in lista:
	print(i)


for i in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.extend([r, l])
	arr.sort()
	arr = arr[arr.index(l) + 1:arr.count(r) + arr.index(r) - 1]
	x = 0
	for i in range(len(arr)):
		if sum(arr[:i + 1]) <= k:
			x = x + 1
		else:
			break
	print(x)


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	ans = 0
	for i in A:
		if i >= l and k >= i and (i <= r):
			k -= i
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, l, r, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	B = [ele for ele in A if l <= ele <= r]
	cnt = 0
	for j in range(len(B)):
		if k - B[j] >= 0:
			k = k - B[j]
			cnt += 1
	print(cnt)


t = int(input())
for i in range(0, t):
	(n, l, r, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	li = -1
	hi = -1
	for i in range(0, n):
		if a[i] >= l:
			li = i
			break
	for i in range(n - 1, -1, -1):
		if a[i] <= r:
			hi = i
			break
	if li == -1 or hi == -1:
		print(0)
	else:
		a1 = a[li:hi + 1]
		summ = 0
		count = 0
		for i in range(0, len(a1)):
			summ = summ + a1[i]
			if summ > k:
				break
			count = count + 1
		print(count)


n = int(input())
for i in range(n):
	(n, l, r, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	list3 = []
	sum1 = 0
	list1.sort()
	list2 = [i for i in list1 if i >= l and i <= r]
	for i in list2:
		sum1 += i
		list3.append(sum1)
	if len(list3) == 0:
		print(0)
	elif list3[len(list3) - 1] < k:
		print(len(list3))
	elif list3[0] > k:
		print(0)
	else:
		for i in list3:
			if i == k:
				print(list3.index(i) + 1)
				break
			elif i > k:
				print(list3.index(i))
				break
			else:
				pass


for _ in range(int(input())):
	(n, l, r, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	i = 0
	s = 0
	ans = 0
	for i in range(n):
		if a[i] < l:
			continue
		if a[i] > r:
			break
		if s + a[i] <= k:
			ans += 1
			s += a[i]
	print(ans)


import math
for i in range(int(input())):
	(n, l, r, K) = map(int, input().split())
	A = [int(k) for k in input().split()]
	m = 0
	A.sort()
	for k in range(n):
		if A[k] <= r and A[k] >= l:
			if K - A[k] >= 0:
				m += 1
				K -= A[k]
			else:
				break
	print(m)


t = int(input())
for zz in range(t):
	(n, p, r, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l = sorted(l)
	c = 0
	s = 0
	for i in range(n):
		if l[i] <= r and l[i] >= p:
			if k - l[i] >= 0:
				c += 1
				k = k - l[i]
	print(c)


import math
tt = int(input())
while tt > 0:
	tt -= 1
	(n, l, r, k) = map(int, input().split(' '))
	v = list(map(int, input().split(' ')))
	a = []
	for i in range(len(v)):
		if v[i] <= r and v[i] >= l:
			a.append(v[i])
	a.sort()
	ans = sum = 0
	for i in range(len(a)):
		if sum + a[i] <= k:
			sum += a[i]
			ans += 1
	print(ans)


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlsit():
	return input().split(' ')

def yes(t):
	if t:
		return 'YES'
	return 'NO'

def solve():
	(n, l, r, k) = intlist()
	c = intlist()
	c = sorted(c)
	total = 0
	tot = 0
	for i in c:
		if i >= l and i <= r and (tot + i <= k):
			total += 1
			tot += i
			continue
		if i >= r or tot >= k:
			break
	return total
t = input()
for tt in range(int(t)):
	print(solve())


test_cases = int(input())
for i in range(test_cases):
	test = 0
	ans = 0
	input1 = list(map(int, input().split()))
	n = input1[0]
	l = input1[1]
	r = input1[2]
	k = input1[3]
	input2 = list(map(int, input().split()))
	input2.sort()
	for i in input2:
		if i <= r and i >= l:
			test += i
			if test <= k:
				ans += 1
	print(ans)


t = int(input())
while t:
	(n, l, r, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	a = []
	for i in arr:
		if i >= l and i <= r:
			a.append(i)
	ans = 0
	while ans < len(a) and k >= a[ans]:
		k -= a[ans]
		ans += 1
	print(ans)
	t -= 1


def FindChocolatesCanBuy(arr, low, high, budget):
	arr = sorted(arr)
	if arr[0] > high:
		return 0
	count = 0
	spend = 0
	for each in arr:
		if low <= each <= high and spend + each <= budget:
			count += 1
			spend += each
	return count
testCases = int(input())
for testCase in range(testCases):
	(size, cheap, expensive, money) = map(int, input().split())
	chocolates = list(map(int, input().split()))
	print(FindChocolatesCanBuy(chocolates, cheap, expensive, money))


t = int(input())
for j in range(0, t):
	(n, l, r, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	arr.sort()
	i = 0
	cnt = 0
	while k > 0 and i < n:
		if arr[i] > r:
			break
		if arr[i] >= l and k - arr[i] >= 0:
			k = k - arr[i]
			cnt += 1
		i = i + 1
	print(cnt)


while True:
	try:
		t = eval(input())
		for i in range(t):
			(n, l1, r, k) = map(int, input().split())
			a = list(map(int, input().split()))
			cnt = 0
			sum1 = 0
			a.sort()
			for j in range(n):
				if sum1 + a[j] <= k and l1 <= a[j] <= r:
					cnt += 1
					sum1 += a[j]
			print(cnt)
	except:
		break


for i in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	chocolate = list(map(int, input().split()))
	chocolate.sort()
	bars = 0
	count = 0
	while k > 0 and count < len(chocolate):
		if l <= chocolate[count] <= r:
			k -= chocolate[count]
			bars += 1
		count += 1
	if k < 0:
		bars -= 1
	print(bars)


for t in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	P = list(map(int, input().split()))
	L = []
	P.sort()
	(S, C) = (0, 0)
	for i in P:
		if i <= r and i >= l:
			L.append(i)
	for j in L:
		S += j
		if S <= k:
			C += 1
	print(C)


t = int(input())
for i in range(t):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	for j in range(len(a)):
		if a[j] >= l and a[j] <= r and (a[j] <= k):
			c = c + 1
			k = k - a[j]
	print(c)


for _ in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	a = list(sorted(map(int, input().split())))
	count = 0
	for i in a:
		if i >= l and i <= r and (k >= i):
			count += 1
			k -= i
	print(count)


for i in range(int(input())):
	(n, l, r, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	count = 0
	sum = 0
	i = 0
	while sum < k and i < n:
		if a[i] >= l and a[i] <= r:
			sum += a[i]
			if sum > k:
				break
			count += 1
		i += 1
	print(count)


for i in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	count = 0
	for item in a:
		if item >= l and item <= r and (item <= k):
			k -= item
			count += 1
	print(count)


q = int(input())
for _ in range(q):
	(ball, dall, ump, doll) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	count = 0
	arr.sort()
	for k in range(len(arr)):
		if arr[k] >= dall:
			if arr[k] <= ump:
				if arr[k] <= doll:
					doll -= arr[k]
					count += 1
	print(count)


for _ in range(int(input())):
	(n, l, r, k) = input().split()
	l = int(l)
	r = int(r)
	s = input().split()
	s_ = []
	for i in range(int(n)):
		if int(s[i]) >= l and int(s[i]) <= r:
			s_.append(int(s[i]))
	flag = True
	k = int(k)
	total = 0
	while s_ != [] and flag:
		if k - min(s_) < 0:
			flag = False
		else:
			total += 1
			k -= min(s_)
			del s_[s_.index(min(s_))]
	print(total)


tests = int(input())
i = 0
while i < tests:
	buy_choc_count = 0
	(n, l, r, k) = (int(x) for x in input().split())
	chocolate_cost = [int(x) for x in input().split()]
	chocolate_cost.sort()
	j = 0
	while j < n:
		if chocolate_cost[j] in range(l, r + 1) and chocolate_cost[j] <= k:
			buy_choc_count += 1
			k -= chocolate_cost[j]
		if chocolate_cost[j] > r:
			break
		j += 1
	print(buy_choc_count)
	i += 1


t = int(input())
for i in range(t):
	(n, l, r, k) = map(int, input().split())
	h = map(int, input().split())
	a = list(h)
	z = 0
	a.sort()
	for i in range(len(a)):
		if a[i] >= l:
			if a[i] <= r:
				if a[i] <= k:
					k -= a[i]
					z += 1
	print(z)


a = int(input())
for i in range(a):
	(n, l, r, k) = map(int, input().split())
	z = list(map(int, input().split()))
	z.sort()
	cnt = 0
	for i in range(len(z)):
		if z[i] >= l and z[i] <= r and (z[i] <= k):
			cnt += 1
			k -= z[i]
	print(cnt)


for t in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	c = 0
	for i in arr:
		if l <= i <= r and i <= k:
			c += 1
			k -= i
	print(c)


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
mod = 10 ** 9 + 7
ANS = []
input = stdin.readline

def solve():
	pass
t = int(input())
for i in range(t):
	(n, l, r, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	total = 0
	totalCost = 0
	for i in range(n):
		if arr[i] >= l and arr[i] <= r and (totalCost + arr[i] <= k):
			total += 1
			totalCost += arr[i]
	ANS.append(str(total))
print('\n'.join(ANS))


def solve():
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for x in a:
		if k <= 0 or x > r:
			break
		if x >= l and x <= k:
			ans += 1
			k -= x
	print(ans)
for test in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, l, r, k) = list(map(int, input().split()))
	ls = list(map(int, input().split()))
	ls.sort()
	ans = 0
	curr = 0
	for i in ls:
		if i >= l and i <= r:
			if curr + i <= k:
				ans += 1
				curr += i
			else:
				break
	print(ans)


t = int(input())
for i in range(t):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	for i in range(n):
		if a[i] >= l and a[i] <= r:
			k -= a[i]
			if k >= 0:
				c += 1
			else:
				break
	print(c)


for i in range(int(input())):
	(a, b, c, d) = list(map(int, input().split()))
	list1 = list(map(int, input().split()))
	list1.sort()
	k = 0
	for q in range(a):
		if list1[q] >= b and list1[q] <= c:
			if d >= list1[q]:
				d -= list1[q]
				k += 1
	print(k)


def f():
	(n, l, r, k) = map(int, input().split())
	g = sorted(map(int, input().split()))
	t = 0
	for i in g:
		if i > k:
			break
		if i >= l and i <= r and (i <= k):
			t += 1
			k -= i
		if i > r:
			break
	return t
for _ in range(int(input())):
	print(f())


for i in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	a = [int(j) for j in input().split()]
	a.sort()
	cnt = 0
	for j in a:
		if j < l or j > r:
			continue
		elif k - j < 0:
			break
		else:
			cnt += 1
			k -= j
	print(cnt)


for t in range(int(input())):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = list(filter(lambda x: r >= x >= l, a))
	a.sort()
	ans = 0
	for i in range(len(a)):
		if a[i] <= k:
			ans += 1
			k -= a[i]
	print(ans)


from collections import *
t = int(input())
for test in range(t):
	(n, l, r, k) = map(int, input().split())
	lks = sorted(list(map(int, input().split())))
	ans = 0
	for i in range(n):
		if k < lks[i]:
			break
		elif lks[i] >= l and lks[i] <= r:
			ans += 1
			k -= lks[i]
	print(ans)


t = int(input())
for tc in range(t):
	(n, l, r, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	res = 0
	cnt = 0
	for i in range(n):
		if arr[i] >= l:
			if arr[i] <= r:
				if cnt + arr[i] <= k:
					res += 1
					cnt += arr[i]
				else:
					break
			else:
				break
	print(res)


T = int(input())
for _ in range(T):
	(n, l, r, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	m = 0
	x = 0
	for i in range(n):
		if l <= A[i] <= r:
			m += A[i]
			if m > k:
				break
			x += 1
	print(x)


import sys

def solve(n, l, r, k, arr):
	arr.sort()
	count = 0
	for i in range(n):
		if k == 0:
			break
		elif arr[i] <= r and arr[i] >= l and (arr[i] <= k):
			k -= arr[i]
			count += 1
	print(count)

def main():
	test_case = int(sys.stdin.readline())
	for tc in range(test_case):
		(n, l, r, k) = map(int, sys.stdin.readline().split())
		arr = [int(a) for a in sys.stdin.readline().split()]
		solve(n, l, r, k, arr)
main()


t = int(input())
for _ in range(t):
	(n, l, r, k) = map(int, input().split())
	a = list(map(int, input().split()))
	res = []
	for i in a:
		if l <= i <= r:
			res.append(i)
	res.sort()
	s = 0
	c = 0
	for i in res:
		if s + i <= k:
			s += i
			c += 1
		else:
			break
	print(c)


k = int(input())
for _ in range(k):
	(n, l, r, k) = map(int, input().split())
	cos = []
	colles = map(int, input().split())
	for c in colles:
		if c >= l and c <= r:
			cos.append(c)
	res = 0
	if len(cos) != 0:
		cos = sorted(cos)
		for c in cos:
			if k >= c:
				k -= c
				res += 1
			else:
				break
	print(res)


import sys

def solve():
	T = int(sys.stdin.readline().rstrip())
	for _ in range(T):
		(n, l, r, k) = list(map(int, sys.stdin.readline().rstrip().split(' ')))
		S = list(map(int, sys.stdin.readline().rstrip().split(' ')))
		possibles = []
		for i in range(n):
			if l <= S[i] <= r:
				possibles.append(S[i])
		possibles.sort()
		money = k
		buys = 0
		for possible in possibles:
			money -= possible
			if money < 0:
				break
			buys += 1
		print(buys)
solve()