Turbulent times are coming, so you decided to buy sugar in advance. There are $n$ shops around that sell sugar: the $i$-th shop sells one pack of sugar for $a_i$ coins, but only one pack to one customer each day. So in order to buy several packs, you need to visit several shops.

Another problem is that prices are increasing each day: during the first day the cost is $a_i$, during the second day cost is $a_i + 1$, during the third day — $a_i + 2$ and so on for each shop $i$.

On the contrary, your everyday budget is only $x$ coins. In other words, each day you go and buy as many packs as possible with total cost not exceeding $x$. Note that if you don't spend some amount of coins during a day, you can't use these coins during the next days.

Eventually, the cost for each pack will exceed $x$, and you won't be able to buy even a single pack. So, how many packs will you be able to buy till that moment in total?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Next $t$ cases follow.

The first line of each test case contains two integers $n$ and $x$ ($1 \le n \le 2 \cdot 10^5$; $1 \le x \le 10^9$) — the number of shops and your everyday budget.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the initial cost of one pack in each shop.

It's guaranteed that the total sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print one integer — the total number of packs you will be able to buy until prices exceed your everyday budget.


-----Examples-----

Input
4
3 7
2 1 2
5 9
10 20 30 40 50
1 1
1
2 1000
1 1
Output
11
0
1
1500


-----Note-----

In the first test case,

Day 1: prices are $[2, 1, 2]$. You can buy all $3$ packs, since $2 + 1 + 2 \le 7$.

Day 2: prices are $[3, 2, 3]$. You can't buy all $3$ packs, since $3 + 2 + 3 > 7$, so you buy only $2$ packs.

Day 3: prices are $[4, 3, 4]$. You can buy $2$ packs with prices $4$ and $3$.

Day 4: prices are $[5, 4, 5]$. You can't buy $2$ packs anymore, so you buy only $1$ pack.

Day 5: prices are $[6, 5, 6]$. You can buy $1$ pack.

Day 6: prices are $[7, 6, 7]$. You can buy $1$ pack.

Day 7: prices are $[8, 7, 8]$. You still can buy $1$ pack of cost $7$.

Day 8: prices are $[9, 8, 9]$. Prices are too high, so you can't buy anything.

In total, you bought $3 + 2 + 2 + 1 + 1 + 1 + 1 = 11$ packs.

In the second test case, prices are too high even at the first day, so you can't buy anything.

In the third test case, you can buy only one pack at day one.

In the fourth test case, you can buy $2$ packs first $500$ days. At day $501$ prices are $[501, 501]$, so you can buy only $1$ pack the next $500$ days. At day $1001$ prices are $[1001, 1001]$ so can't buy anymore. In total, you bought $500 \cdot 2 + 500 \cdot 1 = 1500$ packs.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Sorting

Mathematics

Greedy algorithms


Solutions:
t = int(input())

def solve():
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	cnt = 0
	sum = 0
	for i in range(n):
		sum += arr[i]
		if sum > x:
			break
		cnt += 1 + (x - sum) // (i + 1)
	print(cnt)
for _ in range(t):
	solve()


import math

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

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

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

def printjoin(l, str=False):
	if str:
		l = [str(i) for i in l]
	return ' '.join(l)

def power_of_two(n):
	b = bin(n)[2:]
	return int(b) == 10 ** (len(b) - 1)

def bit_count(n):
	return bin(n).count('1')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	lcm = x * y // gcd(x, y)
	return lcm

def isint(str):
	try:
		int(str)
		return True
	except ValueError:
		return False

def solve():
	(n, x) = intlist()
	a = intlist()
	a = sorted(a)
	s = 0
	ans = 0
	for i in range(n):
		s += a[i]
		if s <= x:
			ans += (x - s) // (i + 1) + 1
	return ans
t = input()
for tt in range(int(t)):
	print(solve())


import sys
input = sys.stdin.readline

def solve():
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	prefixSum = []
	curr = 0
	for num in arr:
		curr += num
		prefixSum.append(curr)
	ans = 0
	for i in range(n):
		if prefixSum[i] > x:
			break
		ans += (x - prefixSum[i]) // (i + 1) + 1
	return ans
for _ in range(int(input())):
	print(solve())


tc = int(input())
for _ in range(tc):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	(an, d) = (0, 0)
	for x in a:
		an += x
		d += 1
		if an > c:
			break
		ans += 1 + (c - an) // d
	print(ans)


def cal(n, x, arr):
	t = [0] * n
	for i in range(n):
		t[i] = t[i - 1] + arr[i]
	if arr[0] > x:
		return 0
	ans = 0
	for i in range(n):
		if t[i] <= x:
			ans += (x - t[i]) // (i + 1) + 1
		else:
			break
	return ans
for jj in range(int(input())):
	(n, x) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	arr.sort()
	print(cal(n, x, arr))


for i in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = 0
	a.sort()
	for i in range(n):
		val = a[i]
		if x >= val:
			x -= val
		else:
			break
		ans += x // (i + 1) + 1
	print(ans)


from itertools import accumulate
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	costs = list(accumulate(a))
	out = 0
	for (i, c) in enumerate(costs):
		d = (x - c) // (i + 1)
		if d >= 0:
			out += d + 1
		else:
			break
	print(out)


def solve():

	def summ(x, i):
		ans = 0
		check = 0
		print(x, i)
		while check < x:
			ans += 1
			check = ans + ans * i
		print(ans)
		return ans
	(n, x) = [int(x) for x in input().split()]
	prices = sorted([int(x) for x in input().split()])
	ans = 0
	for (i, price) in enumerate(prices):
		if price > x:
			break
		ans += (x - price) // (i + 1) + 1
		x -= price
	print(ans)
for tc in range(int(input())):
	solve()


import math
for i in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	sumsofar = 0
	ans = 0
	n = 0
	for i in a:
		n += 1
		sumsofar += i
		if x >= sumsofar:
			ans += 1 + (x - sumsofar) // n
	print(ans)


t = int(input())
for test_case in range(t):
	(n, x) = map(int, input().split())
	a = sorted([int(i) for i in input().split()])
	total = 0
	for i in range(len(a)):
		x -= a[i]
		if x >= 0:
			total += x // (i + 1) + 1
		else:
			break
	print(total)


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	c = sorted(list(map(int, input().split())))
	s = 0
	if min(c) > b:
		print(0)
		continue
	else:
		d = 0
		for i in range(1, a + 1):
			d += c[i - 1]
			if d > b:
				break
			else:
				s += (b - d) // i + 1
		print(s)


def solve():
	(n, x) = map(int, input().strip().split())
	ls = list(map(int, input().strip().split()))
	ls = sorted(ls)
	sm = sum(ls)
	tot = 0
	last = -1
	for i in range(n - 1, -1, -1):
		if x - sm >= 0:
			nxt = (x - sm) // (i + 1)
		else:
			nxt = -1
			assert last == -1
		tot += (i + 1) * (nxt - last)
		last = nxt
		sm -= ls[i]
	return tot
t = int(input())
for _ in range(t):
	print(solve())


t = int(input())
while t:
	t -= 1
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	k = 0
	for i in range(n):
		k += a[i]
		if x - k >= 0:
			ans += (x - k) // (i + 1) + 1
		else:
			break
	print(ans)


from math import floor

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		lst = list(map(int, input().split()))
		lst.sort()
		cum = [0] * n
		cum[0] = lst[0]
		for i in range(1, n):
			cum[i] = cum[i - 1] + lst[i]
		ans = 0
		for i in range(n):
			test = floor((k - cum[i]) / (i + 1)) + 1
			if test < 1:
				break
			ans += test
		print(ans)
main()


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	ans = 0
	for i in range(n):
		if x >= a[i]:
			x -= a[i]
		else:
			break
		ans += x // (i + 1) + 1
	print(ans)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	suma = 0
	booba = 0
	for (k, j) in enumerate(a):
		suma += j
		if not suma > x:
			booba += (x - suma) // (k + 1) + 1
	print(booba)


def helper():
	t = int(input())
	for i in range(t):
		(shops, budget) = [int(x) for x in input().split()]
		arr = [int(x) for x in input().split()]
		arr.sort()
		sm = 0
		arrn = []
		smn = 0
		for i in arr:
			smn += i
			arrn.append(smn)
		for i in range(len(arrn)):
			if budget - arrn[i] >= 0:
				sm += (budget - arrn[i]) // (i + 1) + 1
		print(sm)
helper()


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	su = r = 0
	for i in range(n):
		su += a[i]
		if su > x:
			break
		r += (x - su) // (i + 1) + 1
	print(r)


import sys
input = sys.stdin.readline

def solve():
	pass
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = [int(n) for n in input().split()]
	l.sort()
	count = 0
	s = 0
	for i in range(n):
		s += l[i]
		m = x - s
		if m < 0:
			break
		count += m // (i + 1) + 1
	print(count)


t = int(input())
res = []
for itemT in range(t):
	inp = input().split()
	n = int(inp[0])
	x = int(inp[-1])
	inp2 = input().split()
	a = [int(item) for item in inp2]
	a.sort()
	iSum = 0
	pCount = 0
	for i in range(n):
		iSum += a[i]
		if x - iSum >= 0:
			pCount += (x - iSum) // (i + 1) + 1
		else:
			break
	res.append(pCount)
for i in res:
	print(i)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	s = 0
	ans = 0
	for i in range(n):
		s += a[i]
		if s > x:
			break
		ans += (x - s) // (i + 1) + 1
	print(ans)


def solve():
	(n, money) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	a.sort()
	sum = 0
	for x in a:
		sum += x
	day = -1
	cnt = 0
	for i in range(n - 1, -1, -1):
		val = (money - sum) // (i + 1)
		if val >= 0:
			cnt += (i + 1) * (val - day)
			day = val
		sum -= a[i]
	print(cnt)
for t in range(int(input())):
	solve()


for time in range(int(input())):
	(n, x) = map(int, input().split())
	nums = list(map(int, input().split()))
	nums.sort()
	howa = []
	s = 0
	for j in nums:
		s += j
		if s > x:
			break
		howa.append(s)
	total = 0
	for j in range(len(howa)):
		total += 1 + (x - howa[j]) // (j + 1)
	print(total)


import math

def task(n, x, a):
	a = sorted(a)
	qualified = 0
	amount = 0
	total = 0
	qualified = 0
	for i in range(0, n):
		if amount + a[i] <= x:
			amount += a[i]
			qualified += 1
			total += 1 + math.floor((x - amount) / qualified)
		else:
			break
	print(total)
t = int(input())
for i in range(0, t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	task(n, x, a)


def solve():
	(n, x) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	sum_arr = []
	_ = 0
	for i in arr:
		_ += i
		sum_arr.append(_)
	total = 0
	for i in range(n):
		if sum_arr[i] <= x:
			total += max(0, x - sum_arr[i]) // (i + 1) + 1
	return total
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	c.sort()
	su = 0
	element = 0
	for i in range(1, a + 1, 1):
		su += c[i - 1]
		t = (b - su) // i
		if t >= 0:
			element += t + 1
	print(element)


T = int(input())
for _ in range(T):
	(n, x) = map(int, input().split())
	a = sorted(map(int, input().split()))
	marker = [0]
	for i in range(n):
		marker.append(marker[-1] + a[i])
	start = -1
	ans = 0
	for i in range(1, n + 1):
		if x < marker[i]:
			continue
		else:
			ans += (x - marker[i]) // i + 1
	print(ans)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	s = 0
	x = []
	for i in range(n):
		s = s + l[i]
		if s <= r:
			x.append(r - s)
		else:
			break
	for i in range(len(x)):
		x[i] = x[i] // (i + 1)
	print(sum(x) + len(x))


def pachek(a):
	pass
for t in range(int(input())):
	(n, x) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = []
	sum = 0
	rs = 0
	for i in range(n):
		sum += a[i]
		if sum > x:
			break
		b.append(sum)
	for j in range(len(b)):
		d = (x - b[j]) // (j + 1) + 1
		rs += d
	print(rs)


for it in range(int(input())):
	(n, x) = map(int, input().split())
	a = [0] * n
	i = ans = 0
	for num in input().split():
		a[i] = int(num)
		i += 1
	a.sort()
	if a[0] > x:
		print(0)
	else:
		ans = x - a[0] + 1
		prev = a[0]
		for i in range(1, len(a)):
			prev += a[i]
			add = (x - prev) // (i + 1) + 1
			if add < 0:
				break
			ans += add
		print(ans)


for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = 0
	arr.sort()
	tot = 0
	for i in range(n):
		if tot + arr[i] <= x:
			tot += arr[i]
			ans += (x - tot) // (i + 1) + 1
		else:
			break
	print(ans)


from typing import List

def solve_initial_day(budget: int, costs: List[int]) -> List[int]:
	for (index, cost) in enumerate(costs):
		budget -= cost
		if budget < 0:
			return costs[:index]
	return costs

def solve() -> None:
	(n, x) = map(int, input().split())
	costs = list(map(int, input().split()))
	costs.sort()
	costs = solve_initial_day(x, costs)
	result = 0
	total = sum(costs)
	length = len(costs)
	day = 0
	while costs:
		k = 1 + (x - total) // length
		if k > 0:
			day += k
			result += k * length
		total += k * length
		total -= costs.pop() + day
		length -= 1
	print(result)
for _ in range(int(input())):
	solve()


import math
for i in range(int(input())):
	(n, x) = map(int, input().split())
	A = [int(k) for k in input().split()]
	A.sort()
	d = 0
	if A[0] > x:
		print(0)
	elif A[0] == x:
		print(1)
	else:
		a = A[0]
		d = x - A[0] + 1
		for k in range(1, n):
			a += A[k]
			z = x - a + k + 1
			if z > 0:
				d += z // (k + 1)
			else:
				break
		print(d)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, x) = map(int, input().strip().split())
	l = list(map(int, input().strip().split()))
	l.sort()
	for i in range(1, n):
		l[i] += l[i - 1]
	co = 0
	for i in range(n):
		if x >= l[i]:
			co += (x - l[i]) // (i + 1) + 1
	print(co)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	j = 0
	num = 0
	resta = x
	if num >= 0:
		while j < len(a):
			resta -= a[j]
			if resta >= 0:
				num += resta // (j + 1) + 1
				j += 1
			else:
				break
	else:
		num = 0
	print(num)


t = int(input())
import math
for _ in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	ans = 0
	a = 0
	for i in range(n):
		a += l[i]
		tmp = math.ceil((x - a + 1) / (i + 1))
		if tmp <= 0:
			break
		ans += tmp
	print(ans)


import math
from collections import *
import math

def solve():
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.sort()
	s = sum(a)
	t = n - 1
	c = 0
	l = 0
	d = 0
	while t >= 0:
		if k - s >= 0:
			d = (k - s) // (t + 1) + 1
			l += d
			c += d * (t + 1)
			s += d * (t + 1)
		s = s - (a[t] + l)
		t -= 1
	print(c)
t = int(input())
for _ in range(t):
	solve()


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	b = [0] * (n + 1)
	for i in range(n):
		b[i + 1] = b[i] + a[i]
	(s, res) = (0, 0)
	for i in range(n, 0, -1):
		t = b[i] + s * i
		if k < t:
			continue
		m = (k - t) % i
		res += ((k - t) // i + 1) * i
		s += (k - t) // i + 1
	print(res)
for _ in range(int(input())):
	solve()


T = int(input())
for t in range(T):
	(n, x) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	ans = 0
	cnt = 1
	for a in A:
		if x - a >= 0:
			ans += (x - a) // cnt + 1
			x -= a
			cnt += 1
		else:
			break
	print(ans)


import sys
input = sys.stdin.readline
I = lambda : map(int, input().split())
for _ in [0] * int(input()):
	(_, xin) = I()
	d = {}
	s = val = day = 0
	n = 1
	for i in sorted(list(I())):
		s = i + s
		if s > xin:
			break
		d[n] = (xin - s) // n + 1
		n = n + 1
	for i in reversed(list(d.values())):
		n = n - 1
		val = val + (i - day) * n
		day = i
	print(val)


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for i in range(t):
	(n, budg) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	(pref, summ, ans, d) = ([], 0, 0, 1)
	for i in arr:
		summ += i
		pref.append(summ)
	for i in pref:
		if (budg - i) // d + 1 < 0:
			break
		ans += (budg - i) // d + 1
		d += 1
	print(ans)


T = int(input())
for t in range(T):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	pre = [0] * n
	pre[0] = a[0]
	for i in range(1, n):
		pre[i] = pre[i - 1] + a[i]
	c = 0
	(i, j) = (n - 1, 0)
	while i >= 0:
		if x < pre[i]:
			i -= 1
			continue
		c += (x - pre[i]) // (i + 1) + 1
		i -= 1
	print(c)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	s = 0
	t = []
	f = 0
	for i in range(n):
		s += a[i]
		t.append(s)
		if s > x:
			f = 1
			break
	if f == 0:
		i += 1
	else:
		t.pop()
	for j in range(i):
		ans += (x - t[j]) // (j + 1) + 1
	print(ans)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	pre = [lst[0]]
	for j in lst[1:]:
		pre.append(pre[-1] + j)
	c = 0
	for j in range(n):
		l = j + 1
		if pre[j] <= x:
			rhs = x - pre[j]
			q = rhs // l
			c += q + 1
	print(c)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	for i in range(1, n):
		l[i] += l[i - 1]
	ans = 0
	for i in range(n - 1, -1, -1):
		if x >= l[i]:
			ans += (x - l[i]) // (n - (n - i - 1)) + 1
	print(ans)


t = int(input())
while t > 0:
	(n, x) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	l.sort()
	pack = 0
	for i in range(n):
		if x >= l[i]:
			pack += (x - l[i]) // (i + 1) + 1
			x = x - l[i]
		else:
			break
	print(pack)
	t = t - 1


from math import ceil

def calculate():
	count = 0
	for i in range(n):
		dp[i] = dp[i - 1] + arr[i]
	for i in range(n):
		flag = 0
		if b + 1 - dp[i] > 0:
			count += int(ceil((b + 1 - dp[i]) / (i + 1)))
	return count
T = int(input())
for _ in range(T):
	(n, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	dp = [0] * n
	print(calculate())


import math
for i in range(int(input())):
	(n, x) = map(int, input().split())
	A = [int(k) for k in input().split()]
	A.sort()
	s = []
	if A[0] > x:
		print(0)
	elif A[0] == x:
		print(1)
	else:
		b = []
		b.append(A[0])
		a = A[0]
		for k in range(1, n):
			a += A[k]
			b.append(a)
		m = x - A[0] + 1
		for k in range(1, n):
			z = x - b[k] + k + 1
			if z <= 0:
				break
			else:
				m += z // (k + 1)
		print(m)


import math
for i in range(int(input())):
	(n, x) = list(map(int, input().split()))
	l = sorted(list(map(int, input().split())))
	ans = 0
	if x >= l[0]:
		s = 0
		for (i, a) in enumerate(l):
			s += a
			u = math.floor((x - s) / (i + 1.0)) + 1
			if u > 0:
				ans += u
			else:
				break
	print(ans)


def solution(n, x, W):
	result = 0
	sum = 0
	for (q, t) in enumerate(W):
		sum += t
		result += max(0, (x - sum) // (q + 1) + 1)
	return result
t = int(input())
for q in range(t):
	(n, x) = map(int, input().split())
	W = sorted(map(int, input().split()))
	print(solution(n, x, W))


cases = int(input())
for case in range(cases):
	(n, x) = map(int, input().split())
	shops = list(map(int, input().split()))
	output = 0
	addition = 0
	shops.sort()
	cost = [shops[0]]
	ind = 1
	while ind < n and cost[-1] <= x:
		cost.append(cost[-1] + shops[ind])
		ind += 1
	for i in range(len(cost)):
		if x >= cost[i]:
			output += (x - cost[i]) // (i + 1) + 1
	print(output)


for ii in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	for i in range(1, n):
		a[i] += a[i - 1]
	idx = -1
	for i in range(n):
		if a[i] <= x:
			idx = i
	ans = 0
	for i in range(idx + 1):
		ans += (x - a[i]) // (i + 1) + 1
	print(ans)


import math
for _ in range(int(input())):
	(n, x) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	a = sorted(a)
	som = 0
	size = 1
	ans = 0
	for i in a:
		d = math.floor((x - som - i) / size + 1)
		if d <= 0:
			break
		ans += d
		size += 1
		som += i
	print(ans)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	(ans, ps) = (0, 0)
	for (i, ai) in enumerate(a, 1):
		ans += max(0, (x - ai - ps) // i + 1)
		ps += ai
	print(ans)


N = int(input())
for _ in range(N):
	(n, m) = input().split(' ')
	nums = input().split(' ')
	(n, m) = (int(n), int(m))
	nums = [int(x) for x in nums]
	nums.sort()
	sum = 0
	sum_nums = [0]
	for num in nums:
		sum += num
		sum_nums.append(sum)
	ans = 0
	for i in range(1, n + 1):
		if m - sum_nums[i] >= 0:
			ans += int((m - sum_nums[i]) / i) + 1
	print(ans)


def getSugar(prices, purse, n):
	prices.sort()
	prefixCosts = []
	curr = 0
	sugarPackets = 0
	for i in prices:
		curr += i
		prefixCosts.append(curr)
	for i in range(n):
		if prefixCosts[i] > purse:
			return sugarPackets
		else:
			diff = purse - prefixCosts[i]
			multiplier = diff // (i + 1)
			multiplier += 1
			currPackets = multiplier * (i + 1)
			currPackets -= multiplier * i
			sugarPackets += currPackets
	return sugarPackets
for _ in range(int(input())):
	(n, purse) = map(int, input().split())
	nums = list(map(int, input().split()))
	answer = getSugar(nums, purse, n)
	print(answer)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	l = sum(a)
	days = 0
	buys = 0
	for i in range(n):
		if i:
			l -= a[-i] + days
		if x >= l:
			u = 1 + (x - l) // (n - i)
			buys += u * (n - i)
			days += u
			l += u * (n - i)
	print(buys)


from functools import reduce
t = int(input())
while t:
	t -= 1
	(n, x) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	Sum = reduce(lambda xx, yy: xx + yy, a)
	prev = -1
	a.sort()
	ans = 0
	for i in range(n - 1, -1, -1):
		curday = (x - Sum) // (i + 1) if x - Sum >= 0 else -1
		ans += (i + 1) * (curday - prev)
		prev = curday
		Sum -= a[i]
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	v = list(map(int, input().split()))
	v.sort()
	sum = 0
	noofdaysnow = 0
	noofpreviousdays = 0
	ans = 0
	for i in range(1, n + 1, 1):
		sum = sum + v[i - 1]
		d = (m - sum) // i
		if d >= 0:
			ans += d + 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	count = 0
	pre = []
	pre.append(a[0])
	if n > 1:
		for d in range(1, n):
			pre.append(a[d] + pre[d - 1])
	for k in range(n):
		if pre[k] > x:
			break
		diff = x - pre[k]
		y = diff // (k + 1) + 1
		count += y
	print(count)


def solve():
	arr.sort()
	cumm = [0 for i in range(n)]
	cumm[0] = arr[0]
	for i in range(1, n):
		cumm[i] = cumm[i - 1] + arr[i]
	res = 0
	accum = 0
	i = n - 1
	days = 0
	while i >= 0:
		temp = cumm[i] + days * (i + 1)
		if temp <= x:
			times = (x - temp) // (i + 1)
			res += (i + 1) * (times + 1)
			days += times + 1
		else:
			i -= 1
	return res
T = int(input())
for t in range(T):
	(n, x) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = solve()
	print(ans)


t = int(input())
for _ in range(0, t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	i = 0
	c = 0
	l.sort()
	sum1 = sum(l)
	k = n - 1
	a = [0] * n
	loop = 0
	a[0] = l[0]
	for i in range(1, n):
		a[i] = l[i] + a[i - 1]
	for i in range(n - 1, -1, -1):
		if x < a[i]:
			continue
		else:
			c += int((x - a[i]) / (i + 1)) + 1
	print(c)


T = int(input())
for cid in range(T):
	(N, X) = map(int, input().split())
	R = list(map(int, input().split()))
	R.sort()
	G = 0
	total = 0
	for (i, r) in enumerate(R):
		G += r
		total += max(0, (X - G) // (i + 1) + 1)
	print(total)


import math
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	s = 0
	i = 0
	ans = 0
	while s <= x and i < n:
		s = s + a[i]
		i += 1
	days = 0
	if s > x:
		i -= 1
		s -= a[i]
	pval2 = 0
	ans += i
	while i > 0:
		val = x - s
		val2 = val // i
		ans += i * (val2 - pval2)
		pval2 = val2
		i -= 1
		s = s - a[i]
	print(ans)


t = int(input())
while t:
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	ll = [0] * n
	l.sort()
	p = 0
	ans = 0
	s = 0
	for i in range(n):
		s += l[i]
		if s <= x:
			ll[i] += s
			p += 1
		else:
			break
	for i in range(p):
		ans += (x - ll[i]) // (i + 1) + 1
	print(ans)
	t -= 1


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	arr1 = [arr[0]]
	for i in range(1, n):
		arr1.append(arr1[-1] + arr[i])
	(ans, day) = (0, 0)
	for i in range(n - 1, -1, -1):
		arr1[i] += (i + 1) * day
		if x - arr1[i] >= 0:
			days = (x - arr1[i]) // (i + 1) + 1
			ans += days * (i + 1)
			day += days
	print(ans)


from math import floor
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	p = a.copy()
	for i in range(1, n):
		p[i] += p[i - 1]
	ans = x - a[0] + 1
	if ans < 0:
		print(0)
		continue
	for i in range(1, n):
		t = (x - a[i] - p[i - 1]) // (i + 1) + 1
		if t < 0:
			break
		ans += t
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	m = [0] * n
	l.sort()
	m[0] = l[0]
	for i in range(1, n):
		m[i] = l[i] + m[i - 1]
	y = max(x - l[0] + 1, 0)
	for i in range(1, n):
		if m[i] > x:
			break
		y += max(x - m[i], 0) // (i + 1) + 1
	print(y)


if True:
	t = int(input())
	for _ in range(t):
		(n, x) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		a.sort()
		s = 0
		b = []
		for (i, a_) in enumerate(a):
			s += a_
			b.append(max(1 + (x - s) // (i + 1), 0))
		print(sum(b))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	s = [0]
	for i in range(n):
		s.append(s[-1] + a[i])
	ans = 0
	for i in range(n, 0, -1):
		ans += max(0, (x - s[i]) // i + 1)
	print(ans)


for w in [0] * int(input()):
	(n, x) = map(int, input().split())
	a = sorted(map(int, input().split()))
	f = e = 0
	for (i, y) in enumerate(a):
		f += max(0, (x - y - e) // (i + 1) + 1)
		e += y
	print(f)


for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	a1 = []
	c1 = 0
	t = 0
	t1 = 0
	for i in range(n):
		t += a[i]
		t1 += 1
		if x >= t:
			a1.append((x - t) // t1 + 1)
		else:
			a1.append(0)
	t2 = n
	t3 = 0
	for i in range(n - 1, -1, -1):
		c1 += (a1[i] - t3) * t2
		t2 -= 1
		t3 = a1[i]
	print(c1)


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


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	if a[0] > x:
		print(0)
	else:
		c = x - a[0] + 1
		b = a.copy()
		for i in range(1, n):
			b[i] += b[i - 1]
		for i in range(1, n):
			a1 = x - a[i] - b[i - 1] + i + 1
			if a1 <= 0:
				break
			else:
				c += a1 // (i + 1)
		print(c)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().strip().split()))
	a.sort()
	p = [a[0]]
	for i in range(1, n):
		p.append(p[-1] + a[i])
	c = 0
	for i in range(n - 1, -1, -1):
		h = (x - p[i]) // (i + 1)
		h += 1
		if h > 0:
			c += h
	print(c)


t = int(input())
for i in range(t):
	a = []
	s1 = input().split()
	n = int(s1[0])
	x = int(s1[1])
	s2 = input().split()
	for j in range(n):
		a.append(int(s2[j]))
	a.sort()
	ans = 0
	sum = a[0]
	for j in range(n):
		w = (x - sum) // (j + 1)
		if w >= 0:
			ans += w + 1
		if j != n - 1:
			sum += a[j + 1]
	print(ans)


for _ in [0] * int(input()):
	(n, x) = map(int, input().split())
	a = sorted(map(int, input().split()))
	ans = ps = 0
	for (i, ai) in enumerate(a):
		ans += max(0, (x - ai - ps) // (i + 1) + 1)
		ps += ai
	print(ans)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	v = list(map(int, input().split()))
	v.sort()
	prefix = []
	for i in range(n):
		prefix.append(0)
	s = 0
	for i in range(n):
		s += v[i]
		prefix[i] = s
	ans = 0
	for i in range(n - 1, -1, -1):
		dif = x - prefix[i]
		if dif >= 0 and dif // (i + 1) >= 0:
			ans += dif // (i + 1) + 1
	print(ans)


tc = int(input())
for _ in range(tc):
	(n, x) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	pre = [0]
	for y in a:
		pre.append(pre[-1] + y)
	i = 0
	ans = 0
	for ck in range(n, 0, -1):
		if x >= pre[ck] + i * ck:
			k = (x - (pre[ck] + i * ck)) // ck + 1
			ans += k * ck
			i += k
	print(ans)


from functools import lru_cache

def get_last_term(start, end, d):
	return (end - start) // d + 1
for _ in range(int(input())):
	(shops, b) = map(int, input().split())
	costs = list(map(int, input().split()))
	costs.sort()
	p_sum = []
	s = 0
	for c in costs:
		s += c
		p_sum.append(s)
	ans = 0
	for i in range(len(p_sum)):
		last_term = get_last_term(p_sum[i], b, i + 1)
		if last_term >= 0:
			ans += last_term
	print(ans)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	num = list(map(int, input().split()))
	num.sort()
	ans = tot = 0
	for j in range(n):
		ans += max(0, (x - num[j] - tot) // (j + 1) + 1)
		tot += num[j]
	print(ans)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	l1 = []
	l.sort()
	for j in l:
		c += j
		l1.append(c)
	c = 0
	d = 0
	l2 = []
	for j in range(n):
		if x < l1[j]:
			continue
		l2.append((x - l1[j]) // (j + 1) + 1)
	l2.append(0)
	x = len(l2)
	for j in range(x - 1):
		c += (l2[j] - l2[j + 1]) * (j + 1)
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	S = [0]
	for i in range(n):
		S.append(S[-1] + l[i])
	res = 0
	for i in range(n, 0, -1):
		res += max(0, (k - S[i]) // i + 1)
	print(res)


import math
t = int(input())
for i in range(t):
	n = [int(p) for p in input().split()]
	s = 0
	a = [int(x) for x in input().split()]
	a.sort()
	ans = 0
	b = n[1]
	num = n[0]
	l = []
	for j in range(num):
		s = s + a[j]
		l.append(s)
	for j in range(num):
		if b - l[j] + 1 >= 0:
			ans = ans + math.ceil((b - l[j] + 1) / (j + 1))
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	sumi = 0
	rem = []
	for (index, i) in enumerate(arr):
		sumi += i
		baki = x - sumi
		rem.append(max(0, baki // (index + 1) + 1))
	print(sum(rem))


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	summ = sum(a)
	packs = 0
	k_prev = 0
	val_prev = 0
	for i in range(n, 0, -1):
		k_new = max(0, (x - summ + val_prev) // i + 1)
		packs += i * (k_new - k_prev)
		k_prev = k_new
		val_prev += a[i - 1]
	print(packs)