There are $n$ quests. If you complete the $i$-th quest, you will gain $a_i$ coins. You can only complete at most one quest per day. However, once you complete a quest, you cannot do the same quest again for $k$ days. (For example, if $k=2$ and you do quest $1$ on day $1$, then you cannot do it on day $2$ or $3$, but you can do it again on day $4$.)

You are given two integers $c$ and $d$. Find the maximum value of $k$ such that you can gain at least $c$ coins over $d$ days. If no such $k$ exists, output Impossible. If $k$ can be arbitrarily large, output Infinity.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $n,c,d$ ($2 \leq n \leq 2\cdot10^5$; $1 \leq c \leq 10^{16}$; $1 \leq d \leq 2\cdot10^5$) — the number of quests, the number of coins you need, and the number of days.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — the rewards for the quests.

The sum of $n$ over all test cases does not exceed $2\cdot10^5$, and the sum of $d$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

For each test case, output one of the following.

If no such $k$ exists, output Impossible.

If $k$ can be arbitrarily large, output Infinity.

Otherwise, output a single integer — the maximum value of $k$ such that you can gain at least $c$ coins over $d$ days.

Please note, the checker is case-sensitive, and you should output strings exactly as they are given.


-----Examples-----

Input
6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1
Output
2
Infinity
Impossible
1
12
0


-----Note-----

In the first test case, one way to earn $5$ coins over $4$ days with $k=2$ is as follows:

Day 1: do quest 2, and earn $2$ coins.

Day 2: do quest 1, and earn $1$ coin.

Day 3: do nothing.

Day 4: do quest 2, and earn $2$ coins.

In total, we earned $2+1+2=5$ coins.

In the second test case, we can make over $20$ coins on the first day itself by doing the first quest to earn $100$ coins, so the value of $k$ can be arbitrarily large, since we never need to do another quest.

In the third test case, no matter what we do, we can't earn $100$ coins over $3$ days.

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Greedy algorithms


Solutions:
def bina(l, r, c, d, ss, n):
	m = (l + r + 1) // 2
	if l == r:
		return l
	y = d // (m + 1)
	otv = ss[min(n - 1, m)] * y
	if (m + 1) * y < d:
		otv += ss[min(n, d - y * (m + 1)) - 1]
	if otv >= c:
		return bina(m, r, c, d, ss, n)
	else:
		return bina(l, m - 1, c, d, ss, n)
t = int(input())
for test in range(t):
	(n, c, d) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	x = sum(a[:min(n, d)])
	if x >= c:
		print('Infinity')
	elif a[0] * d < c:
		print('Impossible')
	else:
		ss = [0] * n
		ss[0] = a[0]
		for i in range(1, n):
			ss[i] = ss[i - 1] + a[i]
		print(bina(0, d, c, d, ss, n))


import sys
import math
from bisect import bisect_right as br
from collections import deque

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, v, d) = int_arr()
	arr = int_arr()
	arr.sort(reverse=True)
	p = 0
	sm = []
	for i in range(n):
		p += arr[i]
		sm.append(p)
	if max(arr) * d < v:
		print('Impossible')
		continue
	elif sum(arr[:min(n, d)]) >= v:
		print('Infinity')
		continue
	i = 1
	j = d
	ans = 0
	while i <= j:
		mid = (i + j) // 2
		if mid <= n:
			tot = sm[mid - 1]
			cnt = tot * (d // mid)
			if d % mid != 0:
				cnt += sm[d % mid - 1]
		else:
			tot = sm[n - 1]
			cnt = tot * (d // mid)
			if d % mid != 0:
				cnt += sm[min(n - 1, d % mid - 1)]
		if cnt >= v:
			i = mid + 1
			ans = mid
		else:
			j = mid - 1
	print(ans - 1)


def bin():
	l = 0
	r = 1
	while isok(r):
		r *= 2
	while r - l > 1:
		m = (l + r) // 2
		if isok(m):
			l = m
		else:
			r = m
	return l

def isok(n):
	pz = d // n
	npz = d % n
	sum = pz * p[min(n, len(s))] + p[min(npz, len(s))]
	return sum >= c
for qwer in range(int(input())):
	(n, c, d) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort(reverse=True)
	p = [0]
	for i in s:
		p.append(p[-1] + i)
	if s[0] * d < c:
		print('Impossible')
	elif p[min(len(s), d)] >= c:
		print('Infinity')
	else:
		print(bin() - 1)


def f(k, s, d):
	ck = s[min(k, n - 1)] * (d // (k + 1))
	if d % (k + 1) > 0:
		ck += s[min(d % (k + 1) - 1, n - 1)]
	return ck
T = int(input())
for t in range(T):
	(n, c, d) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort(reverse=True)
	s = [0] * n
	s[0] = a[0]
	for i in range(1, n):
		s[i] = s[i - 1] + a[i]
	if s[min(d - 1, n - 1)] >= c:
		print('Infinity')
		continue
	if s[0] * d < c:
		print('Impossible')
		continue
	l = 0
	r = d
	while r > l:
		k = (l + r + 1) // 2
		ck = f(k, s, d)
		if ck >= c:
			l = k
		else:
			r = k - 1
	print(l)


from itertools import accumulate, dropwhile, count
for _ in range(int(input())):
	(n, c, d) = map(int, input().split())
	rwds = list(sorted(map(int, input().split()), reverse=True))
	sums = [0] + list(accumulate(rwds))
	if sums[min(d, len(rwds))] >= c:
		print('Infinity')
	elif d // len(rwds) * sums[-1] + sums[d % len(rwds)] >= c:
		print(next(dropwhile(lambda k: d // (k + 1) * sums[-1] + sums[min(d % (k + 1), len(rwds))] >= c, count(d * sums[-1] // (c + sums[-1]) - 1))) - 1)
	else:
		try:
			print(next(dropwhile(lambda k: d // (k + 1) * sums[k + 1] + sums[d % (k + 1)] < c, count(len(rwds) - 1, -1))))
		except:
			print('Impossible')


def calc(pre, k, d):
	recur = 0
	if k >= len(pre):
		recur = pre[-1]
	else:
		recur = pre[k - 1]
	cycles = d // k
	leftover = d % k
	add = 0
	if leftover > len(pre):
		add = pre[-1]
	elif leftover == 0:
		add = 0
	else:
		add = pre[leftover - 1]
	return recur * cycles + add
q = int(input())
for o in range(q):
	(n, c, d) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	a.sort()
	a.reverse()
	pre = [0 for i in range(n)]
	cur = 0
	for i in range(len(a)):
		cur += a[i]
		pre[i] = cur
	l = 1
	r = d
	while r - l > 1:
		m = (r + l) // 2
		if calc(pre, m, d) >= c:
			l = m
		else:
			r = m
	if calc(pre, r, d) >= c:
		if r == d:
			print('Infinity')
		else:
			print(r - 1)
	elif calc(pre, 1, d) < c:
		print('Impossible')
	else:
		print(l - 1)


for _ in range(int(input())):
	(n, c, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	zeros = []
	if d > n:
		zeros = [0] * (d - n)
		arr = zeros + arr
	m = len(arr)
	ans = 0
	arr1 = [0] * m
	if arr[m - 1] * d < c:
		ans = 'Impossible'
	elif sum(arr[m - d:m]) >= c:
		ans = 'Infinity'
	else:
		arr1[m - 1] = arr[m - 1]
		for i in range(m - 2, -1, -1):
			arr1[i] = arr1[i + 1] + arr[i]
		for i in range(d, 0, -1):
			que = d // i
			rem = d % i
			if rem > 0:
				if que * arr1[m - i] + arr1[m - rem] >= c:
					ans = i - 1
					break
			elif que * arr1[m - i] >= c:
				ans = i - 1
				break
	print(ans)


def solve():
	(n, c, d) = tuple(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	agg = 0
	for i in range(n):
		if i >= d:
			break
		agg += a[i]
		a[i] = agg
		if agg >= c:
			print('Infinity')
			return
	for i in range(d - 1, -1, -1):
		if a[min(i, n - 1)] * (d // (i + 1)) + (a[min(d % (i + 1) - 1, n - 1)] if d % (i + 1) != 0 else 0) >= c:
			print(str(i))
			return
	print('Impossible')
t = int(input())
for _ in range(t):
	solve()


t = int(input(''))
aas = [0] * t
for j in range(t):
	ncd = input('').split(' ')
	n = int(ncd[0])
	c = int(ncd[1])
	d = int(ncd[2])
	y = input('').split(' ')
	y = sorted([int(z) for z in y])[::-1]
	y += [0] * d
	z = [0] * (n + 1 + d)
	for i in range(n + d):
		z[i + 1] = z[i] + y[i]
	if y[0] * d < c:
		aas[j] = 'Impossible'
	elif z[d] >= c:
		aas[j] = 'Infinity'
	else:
		kmin = 1
		kmax = d
		while kmin + 1 < kmax:
			kmed = (kmin + kmax) // 2
			q = d // kmed
			r = d % kmed
			prof = q * z[kmed] + z[r]
			if prof >= c:
				kmin = kmed
			else:
				kmax = kmed
		aas[j] = kmin - 1
for a in aas:
	print(a)


import sys
input = sys.stdin.readline
for t in range(int(input())):
	(n, c, d) = map(int, input().split())
	lst = list(map(int, input().split()))
	if d > n:
		for i in range(d - n):
			lst.append(0)
	n = len(lst)
	lst.sort()
	lst = lst[n - d:]
	sm = sum(lst)
	if sm >= c:
		sys.stdout.write('Infinity' + '\n')
		continue
	if lst[-1] * d < c:
		sys.stdout.write('Impossible' + '\n')
		continue
	res = []
	temp = 0
	for i in reversed(lst):
		temp += i
		res.append(temp)
	for i in reversed(range(1, d)):
		a = d // i
		b = d % i
		temp = a * res[i - 1]
		if b != 0:
			temp += res[(b - 1) % len(res)]
		if temp >= c:
			sys.stdout.write(str(i - 1) + '\n')
			break


for t in range(int(input())):
	(n, c, d) = map(int, input().split())
	lst = list(map(int, input().split()))
	if d > n:
		for i in range(d - n):
			lst.append(0)
	n = len(lst)
	lst.sort()
	lst = lst[n - d:]
	sm = sum(lst)
	if sm >= c:
		print('Infinity')
		continue
	if lst[-1] * d < c:
		print('Impossible')
		continue
	res = []
	temp = 0
	for i in reversed(lst):
		temp += i
		res.append(temp)
	for i in reversed(range(1, d)):
		a = d // i
		b = d % i
		temp = a * res[i - 1]
		if b != 0:
			temp += res[(b - 1) % len(res)]
		if temp >= c:
			print(i - 1)
			break


import sys
from collections import deque
input = sys.stdin.readline

def valid(mid, l, d, c):
	s = sum(l[:mid])
	temp = s * (d // mid)
	temp += sum(l[:d % mid])
	if temp >= c:
		return True
	else:
		return False

def solve():
	(n, c, d) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	if l[0] * d < c:
		print('Impossible')
	elif sum(l[:d]) >= c:
		print('Infinity')
	else:
		high = d - 1
		low = 1
		result = 1
		while low <= high:
			mid = (low + high) // 2
			if valid(mid, l, d, c):
				result = mid
				low = mid + 1
			else:
				high = mid - 1
		print(result - 1)
t = int(input())
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	(n, c, d) = map(int, input().split())
	A = list(map(int, input().split()))
	A = sorted(A)[::-1]
	if sum(A[:d]) >= c:
		print('Infinity')
	elif A[0] * d < c:
		print('Impossible')
	else:
		(l, r) = (0, d)
		mid = (l + r + 1) // 2
		while l < r:
			selecsum = sum(A[:mid + 1])
			numselec = d // (mid + 1)
			remain = d % (mid + 1)
			coins = numselec * selecsum + sum(A[:remain])
			if coins >= c:
				l = mid
			else:
				r = mid - 1
			mid = (l + r + 1) // 2
		print(mid)


import math

def solution():
	(n, c, d) = [int(i) for i in input().split()]
	nums = [int(i) for i in input().split()]
	nums.sort(reverse=True)
	if c > d * nums[0]:
		print('Impossible')
		return None
	if c <= sum(nums[:d]):
		print('Infinity')
		return None
	sum_num = [0] * n
	sum_num[0] = nums[0]
	for i in range(1, n):
		sum_num[i] = sum_num[i - 1] + nums[i]
	for k in range(1, d + 2):
		(div, mod) = divmod(d, k + 1)
		temp = div * sum_num[min(k, n - 1)]
		if mod > 0:
			temp += sum_num[min(mod - 1, n - 1)]
		if c > temp:
			print(k - 1)
			return None
t = int(input())
while t:
	solution()
	t -= 1


testcase = int(input())
for _ in range(testcase):
	(n, c, d) = [int(num) for num in input().split()]
	arr = [int(num) for num in input().split()]
	arr.sort(reverse=True)
	if sum(arr[:d]) >= c:
		print('Infinity')
		continue
	if arr[0] * d < c:
		print('Impossible')
		continue
	l = 0
	r = d + 1
	while l + 1 < r:
		k = (l + r) // 2
		s0 = sum(arr[d % (k + 1):k + 1])
		s1 = sum(arr[:d % (k + 1)])
		ans = s0 * (d // (k + 1)) + s1 * ((d + k) // (k + 1))
		if ans >= c:
			l = k
		else:
			r = k
	print(l)


import sys
input = sys.stdin.readline
nel = int(input())
for i in range(nel):
	data = list(map(int, input().split(' ')))
	n_quest = data[0]
	n_coins = data[1]
	n_days = data[2]
	data = list(map(int, input().split(' ')))
	rew = sorted(data)[::-1]
	if rew[0] >= n_coins:
		print('Infinity')
		continue

	def getSum(k):
		kk = k + 1
		return sum(rew[:kk]) * (n_days // kk) + sum(rew[:n_days % kk])
	h_k = -1
	if n_days < 100:
		k = 0
		while k < n_days:
			sum_rews = getSum(k)
			if sum_rews >= n_coins:
				h_k = k
			else:
				k = n_days
				break
			k += 1
	else:
		(s, e) = (0, n_days - 1)
		while s <= e:
			m = (s + e) // 2
			val = getSum(m) >= n_coins
			if val:
				s = m + 1
			else:
				e = m - 1
		h_k = s - 1
	if h_k == n_days - 1:
		print('Infinity')
	elif h_k >= 0:
		print(h_k)
	else:
		print('Impossible')


t = int(input())
for _ in range(t):
	a = [int(i) for i in input().split()]
	n = a[0]
	c = a[1]
	d = a[2]
	a = [int(i) for i in input().split()]
	a.sort()
	a = a[::-1]
	if sum(a[:min(n, d)]) >= c:
		print('Infinity')
		continue
	if d * a[0] < c:
		print('Impossible')
		continue
	k1 = 0
	l = 0
	r = d
	while r - l > 1:
		k = (r + l) // 2
		if c <= sum(a[:min(k + 1, n)]) * (d // (k + 1)) + sum(a[:min(n, d % (k + 1))]):
			l = k
			k1 = max(k1, k)
		else:
			r = k
	print(k1)


def calc(v, arr):
	v += 1
	tmp1 = d // v
	tmp2 = d % v
	t = sum(arr[:v])
	tmp_out = tmp1 * t + sum(arr[:tmp2])
	if tmp_out >= c:
		return tmp_out
	else:
		return False

def binarySearch(low, high, out):
	index = (high + low + 1) // 2
	tmp_out = calc(index, arr_sort)
	if high == low:
		return out
	if tmp_out:
		out = max(out, index)
		return binarySearch(index, high, out)
	else:
		return binarySearch(low, index - 1, out)
for _ in range(int(input())):
	(n, c, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr_sort = sorted(arr, reverse=True)
	arr_sort_sum = sum(arr_sort)
	arr_to_d = sum(arr_sort[:d])
	m = max(arr)
	out = 0
	if d * m < c:
		print('Impossible')
	elif arr_to_d >= c:
		print('Infinity')
	else:
		print(binarySearch(0, d, out))


def binary_search(a, days, cnt):
	a = a
	days = days
	cnt = cnt
	l = 0
	r = days
	while r - l != 1:
		m = (r + l) // 2
		temp = sum(a[0:m]) * (days // m) + sum(a[0:days - m * (days // m)])
		if temp >= cnt:
			l = m
		else:
			r = m
	return l - 1
t = int(input())
for p in range(t):
	(n, cnt, days) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	x = sum(a[0:days])
	if x >= cnt:
		print('Infinity')
	elif a[0] * days < cnt:
		print('Impossible')
	else:
		print(binary_search(a, days, cnt))


for __ in range(int(input())):
	(n, c, d) = map(int, input().split())
	a = sorted(list(map(int, input().split())), reverse=True)
	sumlst = [0]
	for i in a:
		sumlst.append(sumlst[-1] + i)
	ans = 'Impossible'
	for k in range(d + 1):
		if sumlst[min(n, k + 1)] * (d // (k + 1)) + sumlst[min(n, d % (k + 1))] >= c:
			ans = k
	print('Infinity' if ans == d else ans)


def check(mid, a, d, c):
	num = mid + 1
	lun = d // num
	lunsum = a[min(num, len(a)) - 1]
	res = lun * lunsum
	yu = d % num
	if yu:
		res += a[min(yu, len(a)) - 1]
	if res >= c:
		return 1
	else:
		return 0

def solve():
	(n, c, d) = input().split(' ')
	n = int(n)
	c = int(c)
	d = int(d)
	a = [int(x) for x in input().split(' ')]
	ff = 0
	if d <= n:
		s = sum(a)
		if s >= c:
			ff = 1
	maxn = max(a)
	if maxn * d < c:
		print('Impossible')
		return
	l = 0
	r = 600000
	a.sort(reverse=True)
	for ev in range(len(a)):
		if ev == 0:
			continue
		a[ev] += a[ev - 1]
	check(1, a, d, c)
	while l < r:
		mid = (l + r + 1) // 2
		if check(mid, a, d, c) == 1:
			l = mid
		else:
			r = mid - 1
	if l == 600000:
		print('Infinity')
	else:
		print(l)
t = int(input())
for each in range(t):
	solve()


for _ in range(int(input())):
	(a, b1, c) = map(int, input().split())
	ls = sorted(list(map(int, input().split())), reverse=True)
	b = [0] * (a + 1)
	for i in range(1, a + 1):
		b[i] = b[i - 1] + ls[i - 1]
	if b[min(a, c)] >= b1:
		print('Infinity')
		continue
	flag = -1
	for i in range(c - 1):
		t = b[min(i + 1, a)] * (c // (i + 1)) + b[min(c % (i + 1), a)]
		if b1 <= t:
			flag = i
		else:
			break
	if flag == -1:
		print('Impossible')
	else:
		print(flag)


t = int(input())
for _ in range(t):
	(n, c, d) = map(int, input().split())
	q = list(map(int, input().split()))
	q.sort(reverse=True)

	def check_k(k):
		blocks = d // (k + 1)
		block_sum = sum(q[:min(k + 1, n)])
		pre_mon = blocks * block_sum
		left_over = d - (k + 1) * blocks
		for i in range(min(left_over, n)):
			pre_mon += q[i]
		return pre_mon >= c
	l = 0
	r = d
	if not check_k(0):
		print('Impossible')
		continue
	if check_k(d):
		print('Infinity')
		continue
	while l < r - 1:
		m = (l + r) // 2
		afn = check_k(m)
		if afn:
			l = m
		else:
			r = m
	print(l)


t = int(input())
for h in range(t):
	(n, c, d) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a, reverse=True)
	b = [0] * (n + 1)
	for i in range(n):
		b[i + 1] = b[i] + a[i]
	f = -1
	for k in range(d + 10):
		s = b[min(k + 1, n)] * (d // (k + 1)) + b[min(d % (k + 1), n)]
		if s >= c:
			f = k
	if f == -1:
		print('Impossible')
	elif f == d + 9:
		print('Infinity')
	else:
		print(f)


from typing import List
from bisect import *
from collections import *
caseNum = int(input())
for i in range(0, caseNum):
	(n, c, d) = [int(v) for v in input().split(' ')]
	quests = [int(v) for v in input().split(' ')]
	quests.sort(reverse=True)
	if c <= sum(quests[:d]):
		print('Infinity')
		continue
	if c > d * quests[0]:
		print('Impossible')
		continue
	k = 0
	pre = [0] * (n + 1)
	pre[0] = quests[0]
	for i in range(1, n):
		pre[i] = pre[i - 1] + quests[i]
	while k <= d:
		t = pre[min(k, n - 1)]
		tempSum = d // (k + 1) * t
		tempSum += pre[min(d % (k + 1) - 1, n - 1)]
		if tempSum < c:
			k -= 1
			break
		k += 1
	print(k)


import math
t = int(input())

def will_it(arr, n, k, c, d):
	if k <= n - 1:
		s = sum(arr[:k + 1])
	else:
		s = sum(arr)
	if d - (k + 1) * (d // (k + 1)) < n:
		required_sum = sum(arr[:d - (k + 1) * (d // (k + 1))])
	else:
		required_sum = sum(arr)
	if s * (d // (k + 1)) + required_sum >= c:
		return True
	else:
		return False

def solve():
	(n, c, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	if arr[0] * d < c:
		print('Impossible')
	else:
		s = 0
		days = -1
		for i in range(n):
			s += arr[i]
			if arr[i] >= c:
				days = i + 1
				break
		if days != -1 and days <= d:
			print('Infinity')
		else:
			low = 0
			up = 1000000
			ans = 0
			while low <= up:
				mid = low + (up - low) // 2
				if will_it(arr, n, mid, c, d):
					low = mid + 1
					ans = max(ans, mid)
				else:
					up = mid - 1
			print(ans if up < 1000000 else 'Infinity')
while t:
	solve()
	t -= 1


import sys
from sys import stdin
import heapq
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
input = sys.stdin.readline
t = int(input())
res = []

def solution(d, k, len, lis):
	(sum, ans) = (0, 0)
	for i in range(min(len, k + 1)):
		sum += lis[i]
	ans = sum * (d // (k + 1))
	for i in range(min(len, d % (k + 1))):
		ans += lis[i]
	return ans
for _ in range(t):
	(n, c, d) = map(int, input().split())
	lis = list(map(int, input().split()))
	lis.sort(reverse=True)
	if lis[0] * d < c:
		res.append('Impossible')
		continue
	sum = 0
	for i in range(min(n, d)):
		sum += lis[i]
	if sum >= c:
		res.append('Infinity')
		continue
	(l, r) = (0, d)
	while r - l > 1:
		mid = (l + r) // 2
		if solution(d, mid, n, lis) < c:
			r = mid
			continue
		else:
			l = mid
			continue
	res.append(l)
print(*res, sep='\n')


arr = [4, 4, 2, 1, 2, 2]
d = 8
c = 22

def check(k):
	num = min(k, len(arr) - 1)
	num = min(d - 1, num)
	multi = d // (k + 1)
	modul = d % (k + 1)
	modul = min(modul, len(arr))
	sum = 0
	for i in range(0, num + 1):
		sum += arr[i]
	if multi > 0:
		sum *= multi
	if modul > 0:
		for i in range(modul):
			sum += arr[i]
	return sum
t = int(input())
while t > 0:
	t -= 1
	(n, c, d) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	(l, r) = (0, d)
	maxK = -1
	arr.sort(reverse=True)
	while l <= r:
		mid = (l + r) // 2
		sum = check(mid)
		if sum >= c:
			l = mid + 1
			maxK = max(maxK, mid)
		else:
			r = mid - 1
	if l >= d:
		print('Infinity')
	elif maxK >= 0:
		print(maxK)
	else:
		print('Impossible')


inf = 2 ** 60
for tcase in range(int(input())):
	(n, c, d) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	a = [0] + a
	for i in range(n):
		a[i + 1] += a[i]
	(l, r) = (-1, inf)
	while r - l > 1:
		k = (l + r) // 2
		(d1, d2) = divmod(d, k + 1)
		if c <= a[min(n, k + 1)] * d1 + a[min(n, d2)]:
			l = k
		else:
			r = k
	if l > inf // 3:
		print('Infinity')
	elif l < 0:
		print('Impossible')
	else:
		print(l)


t = int(input())

def possible(k, n, c, d, nums):
	ssum = 0
	for i in range(d):
		try:
			a = nums[i % (k + 1)]
		except:
			a = 0
		ssum += a
	return ssum >= c

def solve():
	(n, c, d) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	nums.sort(reverse=True)
	l = 0
	r = d - 1
	if sum(nums[:min(d, n, len(nums))]) >= c:
		print('Infinity')
		return
	while True:
		if r - l <= 3:
			for k in range(r, l - 1, -1):
				if possible(k, n, c, d, nums):
					print(k)
					return
			print('Impossible')
			return
		k = (l + r) // 2
		pos = possible(k, n, c, d, nums)
		if pos:
			l = k
		else:
			r = k - 1
for _ in range(t):
	solve()


T = int(input())
while T > 0:
	T -= 1
	(n, c, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	aoi = sorted(arr, reverse=True)
	l = 1
	r = d + 1
	sum = 0
	for i in range(len(aoi)):
		sum += aoi[i]

	def check(k):
		sana = 0
		for i in range(d):
			if i % k < n:
				sana += aoi[i % k]
		return sana >= c
	while l < r:
		m = (l + r) // 2
		if check(m):
			l = m + 1
		else:
			r = m
	if l == 1:
		print('Impossible')
	elif l == d + 1:
		print('Infinity')
	else:
		print(l - 2)


t = int(input())
while t > 0:
	(n, c, d) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	a.sort(reverse=True)
	(left, right) = (0, d + 2)
	while left < right:
		mid = left + (right - left + 1) // 2
		total = 0
		current = 0
		for i in range(d):
			if i % mid < n:
				total += a[i % mid]
		if total >= c:
			left = mid
		else:
			right = mid - 1
	if left == d + 2:
		print('Infinity')
	elif left == 0:
		print('Impossible')
	else:
		print(left - 1)
	t -= 1


import sys
input = sys.stdin.readline

def solve():
	(N, C, D) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	A.sort()
	i = N - 1
	temp = 0
	for _ in range(min(D, N)):
		temp += A[i]
		i -= 1
		if temp >= C:
			print('Infinity')
			return
	if D * A[-1] < C:
		print('Impossible')
		return
	A.reverse()
	ans = 0
	(l, r) = (0, D - 1)
	while l <= r:
		mid = (l + r) // 2
		k = mid + 1
		t = 0
		j = 0
		while j < D:
			if j % k < N:
				t += A[j % k]
				j += 1
			else:
				j += k - j % k
		if t >= C:
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	print(ans)
for _ in range(int(input())):
	solve()


def compute_max(numbers, k, d, n):
	sum = 0
	for i in range(d):
		if i % (k + 1) < n:
			sum += numbers[i % (k + 1)]
	return sum
t = int(input())
while t > 0:
	ncd = [int(x) for x in input().split()]
	n = ncd[0]
	c = ncd[1]
	d = ncd[2]
	list_of_numbers = [int(x) for x in input().split()]
	list_of_numbers.sort(reverse=True)
	show_infinity = sum(list_of_numbers[:min(d, n)])
	if show_infinity >= c:
		print('Infinity')
	elif list_of_numbers[0] * d < c:
		print('Impossible')
	else:
		left = 0
		right = d - 1
		ans = 0
		while left <= right:
			middle = int((left + right) / 2)
			max_coins = compute_max(list_of_numbers, middle, d, n)
			if max_coins >= c:
				ans = middle
				left = middle + 1
			if max_coins < c:
				right = middle - 1
		print(ans)
	t = t - 1


T = int(input())
for hasbulla in range(T):
	(n, c, d) = [int(x) for x in map(int, input().split())]
	t = list(map(int, input().split()))
	t.sort(reverse=True)
	if t[0] * d < c:
		print('Impossible')
		continue
	l = 0
	r = d + 9
	ans = 0
	while l != r:
		mid = (l + r) // 2
		essa = 0
		for i in range(d):
			if i % mid < n:
				essa += t[i % mid]
		if essa >= c:
			l = mid + 1
			ans = mid
		else:
			r = mid
	if ans == d + 8:
		print('Infinity')
		continue
	print(ans - 1)


test = int(input())
from itertools import accumulate
while test:
	(n, c, d) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort(reverse=True)
	pre_sum = list(accumulate(a))
	low = -1
	high = d + 1
	while low < high:
		mid = low + high + 1 >> 1
		curr_coins = 0
		for i in range(d):
			ind = i % (mid + 1)
			if ind < n:
				curr_coins += a[ind]
		if curr_coins >= c:
			low = mid
		else:
			high = mid - 1
	if low == -1:
		print('Impossible')
	elif low == d + 1:
		print('Infinity')
	else:
		print(low)
	test -= 1


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n, c, d):
	if sum(a[:min(d, n)]) >= c:
		return 'Infinity'
	if d * a[0] < c:
		return 'Impossible'

	def count(k):
		ans = 0
		visited = set()
		for (i, x) in enumerate(a):
			j = i
			while j < d and j not in visited:
				ans += x
				visited.add(j)
				j += k + 1
		return ans
	(l, r) = (0, d)
	while l < r:
		k = (l + r + 1) // 2
		if count(k) >= c:
			l = k
		else:
			r = k - 1
	return l
t = int(input())
for _ in range(t):
	(n, c, d) = map(int, input().split())
	a = sorted(map(int, input().split()))[::-1]
	print(solve(a, n, c, d))


t = int(input())
for i in range(t):
	(n, c, d) = [int(x) for x in input().split()]
	L = [int(x) for x in input().split()]
	L.sort(reverse=True)
	(l, r) = (0, 10 ** 15)
	while l < r:
		m = (l + r + 1) // 2
		if m == 0:
			l = 0
			break
		if sum(L[:min(m, n)]) * (d // m) + sum(L[:min(d % m, n)]) >= c:
			l = m
		else:
			r = m - 1
	print(l - 1 if l != 10 ** 15 and l != 0 else 'Infinity' if r == 10 ** 15 else 'Impossible')


def binp(b, m, c, y):
	if b[c] >= m and b[c - 1] < m:
		return c
	elif b[c] > m:
		return binp(b, m, c - y, max(y // 2, 1))
	elif b[c] < m:
		return binp(b, m, c + y, max(y // 2, 1))
for _ in range(int(input())):
	(n, c, d) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	ans = -1
	s = 0
	b = [0]
	I = -1
	i = 0
	while True:
		if i < n:
			s += a[i]
			b.append(s)
			w = c // s * (i + 1) + (binp(b, c % s, len(b) // 2, max(len(b) // 2 // 2, 1)) if c % s > 0 else 0)
		elif c % s == 0:
			w = (c // s - 1) * (i + 1) + len(b) - 1
		else:
			w = c // s * (i + 1) + (binp(b, c % s, len(b) // 2, max(len(b) // 2 // 2, 1)) if c % s > 0 else 0)
		if c <= s and i + 1 <= d:
			I = 1
			break
		if w <= d:
			ans = i
		else:
			break
		i += 1
	if I == 1:
		print('Infinity')
	elif ans > -1:
		print(ans)
	else:
		print('Impossible')


def N():
	return int(input())

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

def S():
	return input()
for _ in range(N()):
	(n, c, d) = A()
	l = 0
	if 'codeforces' == 28226329:
		print('Tanmay')
	a = A()
	h = 10 ** 18
	a.sort()
	a.reverse()
	while l < h:
		k = (h + 1 + l) // 2
		if c > d // k * sum(a[:min(k, n)]) + sum(a[:min(d % k, n)]):
			h = k - 1
		else:
			l = k
	if l == 10 ** 18:
		print('Infinity')
		continue
	if l == 0:
		print('Impossible')
		continue
	print(l - 1)


import math
for _ in range(int(input())):
	(n, c, d) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)

	def works(k):
		sum1 = 0
		for i in range(min(k, n)):
			sum1 += a[i]
		poss = d // k * sum1 + sum(a[:min(d % k, n)])
		return poss >= c
	lo = 0
	hi = 10 ** 18
	while lo < hi:
		mid = (lo + hi + 1) // 2
		if works(mid):
			lo = mid
		else:
			hi = mid - 1
	print('Impossible' if lo == 0 else 'Infinity' if lo == 10 ** 18 else lo - 1)