Minion Chef likes to eat bananas a lot. There are N piles of bananas in front of Chef; for each i (1 ≤ i ≤ N), the i-th pile contains Ai bananas.
Chef's mother wants her to eat the bananas and be healthy. She has gone to the office right now and will come back in H hours. Chef would like to make sure that she can finish eating all bananas by that time.
Suppose Chef has an eating speed of K bananas per hour. Each hour, she will choose some pile of bananas. If this pile contains at least K bananas, then she will eat K bananas from it. Otherwise, she will simply eat the whole pile (and won't eat any more bananas during this hour).
Chef likes to eat slowly, but still wants to finish eating all the bananas on time. Therefore, she would like to choose the minimum K such that she is able to eat all the bananas in H hours. Help Chef find that value of K.

-----Input-----
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N and H denoting the number of piles and the number of hours after which Chef's mom will come home.
- The second line contains N space-separated integers A1, A2, ..., AN.

-----Output-----
For each test case, print a single line containing one integer — the minimum possible value of K.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- N ≤ H ≤ 109
- 1 ≤ Ai ≤ 109 for each valid i

-----Subtasks-----
Subtask #1 (30 points):
- 1 ≤ N ≤ 100
- Ai ≤ 103 for each valid i

Subtask #2 (70 points): original constraints

-----Example-----
Input:

3
3 3
1 2 3
3 4
1 2 3
4 5
4 3 2 7

Output:

3
2
4

-----Explanation-----
Example case 1: With a speed of K = 3 bananas per hour, Chef can finish eating all the bananas in 3 hours. It's the minimum possible speed with which she can eat all the bananas in 3 hours. With a speed of 2 bananas per hour, she would take at least 4 hours and with a speed of 1 banana per hour, she would take at least 6 hours.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Complete search


Solutions:
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	(l, r) = (1, 1000000000)
	while l < r:
		k = (l + r) // 2
		if sum([i // k + int(i % k != 0) for i in arr]) <= h:
			r = k
		else:
			l = k + 1
	print(l)


import math

def b(l, s, h):
	o = 0
	for i in l:
		o += math.ceil(i / s)
	if o <= h:
		return True
	else:
		return False
t = int(input())
for z in range(t):
	(n, h) = map(int, input().split())
	l = list(map(int, input().split()))
	q = 1
	r = max(l)
	while q != r:
		s = (q + r) // 2
		if b(l, s, h):
			r = s
		else:
			q = s + 1
	print(r)


import math
T = int(input())
for _ in range(T):
	(N, H) = map(int, input().split())
	A = list(map(int, input().split()))
	(low, high) = (1, max(A))
	while low != high:
		time = 0
		mid = (low + high) // 2
		for i in range(N):
			time += math.ceil(A[i] / mid)
		if time <= H:
			high = mid
		else:
			low = mid + 1
	print(high)


import math

def isvalid(l, m, k):
	c = 0
	for i in l:
		c += math.ceil(i / m)
	if c <= k:
		return True
	else:
		return False
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 1
	e = max(l)
	ans = -1
	while s <= e:
		m = (s + e) // 2
		if isvalid(l, m, k):
			ans = m
			e = m - 1
		else:
			s = m + 1
	print(ans)


from math import ceil

def minions(arr1, mid1, h1):
	csum = 0
	for i in arr1:
		csum += ceil(i / mid1)
		if csum > h1:
			return False
	return True
t = int(input())
while t > 0:
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	i = 1
	j = max(arr)
	mini = j
	while i <= j:
		mid = (i + j) // 2
		if minions(arr, mid, h):
			if mid < mini:
				mini = mid
				j = mid - 1
			else:
				break
		else:
			i = mid + 1
	print(mini)
	t = t - 1


import math

def koko(arr, h):
	lo = 0
	hi = max(arr)
	res = 0
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if isvalid(arr, h, mid):
			res = mid
			hi = mid - 1
		else:
			lo = mid + 1
	return res

def isvalid(arr, h, k):
	su = 0
	for i in range(len(arr)):
		if k == 0:
			return False
		su += math.ceil(arr[i] / k)
		if su > h:
			return False
	return True

def main():
	koko(arr, h)
t = int(input())
while t:
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(koko(arr, h))
	t -= 1


from math import *

def bisekcija():
	lo = 1
	hi = max(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if moze(mid, a, H):
			hi = mid
		else:
			lo = mid + 1
	return lo

def moze(K, a, H):
	s = 0
	for i in a:
		s = s + ceil(i / K)
	if s > H:
		return False
	else:
		return True
for i in range(int(input())):
	(n, H) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	print(bisekcija())


import math

def return_K(arr, K):
	tot = 0
	for i in range(len(arr)):
		tot += math.ceil(arr[i] / K)
	return tot
for _ in range(int(input())):
	(N, H) = map(int, input().split())
	arr = list(map(int, input().split()))
	l = 1
	h = max(arr)
	ans = -1
	while l <= h:
		mid = (l + h) // 2
		cnt = return_K(arr, mid)
		if cnt > H:
			l = mid + 1
		else:
			ans = mid
			h = mid - 1
	print(ans)


import math
T = int(input())
while T:
	s = input().split()
	n = int(s[0])
	h = int(s[1])
	arr = [int(i) for i in input().split()]
	beg = 1
	end = max(arr)
	k = 0
	while beg <= end:
		mid = (beg + end) // 2
		hrs = 0
		for i in arr:
			hrs += math.ceil(i / mid)
		if hrs <= h:
			ans = mid
			end = mid - 1
		else:
			beg = mid + 1
	print(ans)
	T = T - 1


import math
for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	m = math.ceil(sum(a) / k)
	if k == n:
		print(max(a))
	else:
		for i in range(m, max(a) + 1):
			s = 0
			for j in a:
				s += math.ceil(j / i)
			if s <= k:
				print(i)
				break


def MinimumHours(n, h, a):
	a.sort()
	b = a[0]
	c = 0
	s = 0
	j = 0
	m = 1
	while 1:
		for i in a[-1:-(n + 2):-1]:
			if i % m == 0:
				s += i // m
			else:
				s += i // m + 1
			if s > h:
				break
		if s <= h:
			return m
		m += 1
		s = 0
p = []
for i in range(int(input())):
	(n, h) = input().split()
	p.append(MinimumHours(int(n), int(h), [int(i) for i in input().split()]))
for i in p:
	print(i)


import math

def check(a, k, h):
	t = 0
	for el in a:
		t += math.ceil(el / k)
		if t > h:
			return False
	return True

def bsearch(a, h):
	(lo, hi) = (1, max(a))
	ans = -1
	while lo <= hi:
		mid = hi + (lo - hi) // 2
		if check(a, mid, h):
			ans = mid
			hi = mid - 1
		else:
			lo = mid + 1
	return ans
for i in range(int(input())):
	(n, h) = map(int, input().split())
	a = [int(i) for i in input().split()]
	print(bsearch(a, h))


from math import ceil

def banana(s, b, limit):
	r = 0
	for i in s:
		r += ceil(i / b)
	if r <= limit:
		return True
	else:
		return False
test = int(input())
for _ in range(test):
	(n, h) = map(int, input().split())
	s = list(map(int, input().split()))
	t = 1
	c = max(s)
	while t != c:
		b = (t + c) // 2
		if banana(s, b, h):
			c = b
		else:
			t = b + 1
	print(t)


from math import ceil

def sum_k(arr, k):
	su = 0
	for i in arr:
		su += ceil(i / k)
	return su
for _ in range(int(input())):
	(n, h) = tuple(map(int, input().split()))
	a = list(map(int, input().split()))
	(low, high) = (0, max(a) - 1)
	count = 0
	while low <= high:
		mid = (low + high) // 2
		if sum_k(a, mid + 1) > h:
			low = mid + 1
			count = mid + 1
		else:
			high = mid - 1
	print(count + 1)


def godFunc(arr, k, h):
	noh = sum([i // k + int(i % k != 0) for i in arr])
	return noh <= h
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	(l, r) = (1, 1000000000)
	while l < r:
		mid = (l + r) // 2
		if godFunc(arr, mid, h):
			r = mid
		else:
			l = mid + 1
	print(l)


from math import ceil
for i in range(int(input())):
	(n, h) = map(int, input().split())
	l1 = list(map(int, input().split()))
	k = None
	l = 1
	r = max(l1)
	while l < r:
		m = (l + r) // 2
		k1 = m
		t = 0
		for i in range(n):
			t += ceil(l1[i] / k1)
		if t > h:
			l = m + 1
		else:
			r = m
	print(r)


from math import *

def check(arr, n, mid):
	l = 0
	for i in range(n):
		l += ceil(arr[i] / mid)
	return l
for u in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	(x, y) = (1, max(l))
	while x != y:
		m = (x + y) // 2
		s = check(l, n, m)
		if s <= k:
			y = m
		else:
			x = m + 1
	print(x)


from math import ceil

def within(l, k, h):
	s = 0
	for i in range(len(l)):
		t = ceil(l[i] / k)
		s += t
	if s <= h:
		return True
	else:
		return False
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	l = list(map(int, input().split()))
	l_1 = 1
	r_1 = max(l)
	while l_1 != r_1:
		mid = l_1 + (r_1 - l_1) // 2
		if within(l, mid, h) == True:
			r_1 = mid
		else:
			l_1 = mid + 1
	print(l_1)


from math import ceil

def is_ans(arr, k, h):
	count = 0
	for i in arr:
		count += ceil(i / k)
	if count <= h:
		return True
	else:
		return False
t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	li = list(map(int, input().split()))
	lo = 1
	hi = max(li)
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if is_ans(li, mid, h):
			ans = mid
			hi = mid - 1
		else:
			lo = mid + 1
	print(ans)


import math
T = int(input())
for _ in range(T):
	(n, h) = map(int, input().split())
	a = list(map(int, input().split()))
	k = 0
	mini = 1
	maxi = max(a)
	mid = (mini + maxi) // 2
	while mini < maxi:
		mid = (mini + maxi) // 2
		total = 0
		for i in a:
			total = total + math.ceil(i / mid)
		if total <= h:
			k = mid
			maxi = mid
		else:
			mini = mid + 1
	print(max(mini, mid))


from math import ceil

def cal(v):
	val = 0
	for i in A:
		val += ceil(i / v)
	return val
for _ in range(int(input())):
	(N, H) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	A.sort()
	(lb, ub) = (1, A[N - 1])
	while lb <= ub:
		mid = (lb + ub) // 2
		val = cal(mid)
		if val <= H:
			ans = mid
			ub = mid - 1
		else:
			lb = mid + 1
	print(ans)


import math
for i in range(int(input())):
	(n, h) = map(int, input().split())
	a = [int(j) for j in input().split()]
	left = 1
	right = max(a)
	ans = 0
	while left <= right:
		mid = left + (right - left) // 2
		sum = 0
		for j in a:
			sum += math.ceil(j / mid)
		if sum > h:
			left = mid + 1
		elif sum <= h:
			ans = mid
			right = mid - 1
	else:
		print(ans)


import math

def bsearch(lst, m, h):
	l = 1
	r = m
	ans = r
	while l <= r:
		mid = (l + r) // 2
		if check(lst, mid, h):
			ans = min(ans, mid)
			r = mid - 1
		else:
			l = mid + 1
	return ans

def check(lst, x, h):
	s = 0
	for i in lst:
		s += math.ceil(i / x)
	return s <= h
t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	lst = list(map(int, input().split()))
	tag = max(lst)
	ans = bsearch(lst, tag, h)
	print(ans)


from math import ceil

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

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

def Input():
	return input()
for test in range(int(input())):
	(n, h) = listInput()
	arr = listInput()
	(l, r) = (1, max(arr))
	while l < r:
		m = (l + r) // 2
		s = 0
		k = m
		for i in range(n):
			s += ceil(arr[i] / k)
		if s <= h:
			r = m
		else:
			l = m + 1
	print(l)


import math
for tc in range(int(input())):
	(n, h) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	if n == h:
		print(max(l))
	else:
		k = math.ceil(s / h)
		r = max(l)
		while k < r:
			m = (k + r) // 2
			s = 0
			for j in l:
				s += math.ceil(j / m)
			if s <= h:
				r = m
			else:
				k = m + 1
		print(k)


from math import ceil

def is_possible(a, val, h):
	ct = 0
	for elem in a:
		ct += ceil(elem / val)
	return ct <= h

def binarySearch(n, h, a):
	mmin = 1
	mmax = max(a)
	while mmin <= mmax:
		mid = (mmin + mmax) // 2
		if is_possible(a, mid, h):
			mmax = mid - 1
		else:
			mmin = mid + 1
	return mmin
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = binarySearch(n, h, a)
	print(ans)


import math
for _ in range(int(input())):
	(N, H) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = max(A)
	l = 1
	hi = max(A)
	while l <= hi:
		i = (l + hi) // 2
		c = 0
		for j in range(N):
			c += math.ceil(A[j] / i)
		if c <= H:
			ans = min(ans, i)
			hi = i - 1
		else:
			l = i + 1
	print(ans)


def MinimumHours(n, h, a):
	a.sort()
	j = 0
	mi = a[j]
	s = 0
	c = 0
	c2 = 0
	while 1:
		for i in a[-1:-(n + 2):-1]:
			if i % mi == 0:
				s += i // mi
			else:
				s += i // mi + 1
			if s > h:
				c = 1
				if c2 == 1:
					return mi + 1
				break
		if c2 == 0 and c == 1:
			pmi = mi
			j += 1
			mi = a[j]
			c = 0
			s = 0
			continue
		c2 = 1
		mi -= 1
		s = 0
p = []
for i in range(int(input())):
	(n, h) = input().split()
	p.append(MinimumHours(int(n), int(h), [int(i) for i in input().split()]))
for i in p:
	print(i)


from math import ceil
ans = []
for _ in range(int(input())):
	(N, H) = map(int, input().strip().split())
	Ai = list(map(int, input().strip().split()))

	def canEat(k: int):
		total = 0
		for v in Ai:
			total += ceil(v / k)
		return total <= H
	left = 1
	right = max(Ai)
	while left < right:
		m = left + (right - left) // 2
		if left == m or right == m:
			break
		if canEat(m):
			right = m
		else:
			left = m
	ans.append(right)
print(*ans, sep='\n')


from math import ceil
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	low = 1
	high = max(arr)
	while low != high:
		mid = (low + high) // 2
		check = 0
		for i in arr:
			check += ceil(i / mid)
		if check <= h:
			high = mid
		else:
			low = mid + 1
	print(low)


from math import ceil

def eat_complete(bananas, k, h):
	elapsed = 0
	for pile in bananas:
		elapsed += ceil(pile / k)
		if elapsed > h:
			return False
	return True
for _ in range(int(input())):
	(length, time) = map(int, input().split())
	arr = sorted(list(map(int, input().split())), reverse=True)
	i = 1
	j = arr[0]
	min_k = j
	while i <= j:
		m = (i + j) // 2
		if eat_complete(arr, m, time):
			if m < min_k:
				min_k = m
				j = m - 1
			else:
				break
		else:
			i = m + 1
	print(min_k)


from math import ceil

def is_valid_k(k, l, h):
	s = 0
	for i in l:
		s += ceil(i / k)
	if s <= h:
		return True
	return False
t = int(input())
for i in range(t):
	(n, h) = map(int, input().split())
	l = list(map(int, input().split()))
	lo = 1
	hi = max(l)
	while lo < hi:
		mid = int(lo + (hi - lo) / 2)
		valid = is_valid_k(mid, l, h)
		if valid:
			hi = mid
		else:
			lo = mid + 1
	print(lo)


def MinimumHours(n, h, a):
	a.sort()
	pmi = a[-1]
	mi = a[-1]
	s = 0
	while 1:
		for i in a:
			if i % mi == 0:
				s += i // mi
			else:
				s += i // mi + 1
		if s <= h:
			pmi = mi
			mi -= 1
			s = 0
			continue
		return pmi
p = []
for i in range(int(input())):
	(n, h) = input().split()
	p.append(MinimumHours(int(n), int(h), [int(i) for i in input().split()]))
for i in p:
	print(i)


from bisect import bisect_left

def searchCandies(a, n, k, ho):
	(l, h, m) = (1, 1000000000, 0)
	while l <= h:
		(m, s) = ((l + h) // 2, 0)
		for i in range(n):
			if a[i] % m != 0:
				s += a[i] // m + 1
			else:
				s += a[i] // m
		if s > ho:
			l = m + 1
		else:
			h = m - 1
	return l

def main():
	t = int(input())
	for w in range(t):
		(n, h) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		print(searchCandies(a, n, max(a), h))
main()


def MinimumHours(n, h, a):
	a.sort()
	j = 0
	mie = 2
	mio = 1
	s1 = 0
	s2 = 0
	c1 = 0
	c2 = 0
	while 1:
		for i in a[-1:-(n + 1):-1]:
			if i % mie == 0:
				s1 += i // mie
			else:
				s1 += i // mie + 1
			if i % mio == 0:
				s2 += i // mio
			else:
				s2 += i // mio + 1
			if s1 > h:
				c1 = 1
			if s2 > h:
				c2 = 1
			if c1 == c2 == 1:
				break
		if c1 == c2 == 1:
			c1 = 0
			s1 = 0
			c2 = 0
			s2 = 0
			mie += 2
			mio += 2
		else:
			if c2 == c1 == 0:
				return min(mie, mio)
			if c1 == 0:
				return mie
			return mio
p = []
for i in range(int(input())):
	(n, h) = input().split()
	p.append(MinimumHours(int(n), int(h), [int(i) for i in input().split()]))
for i in p:
	print(i)


def trace(bIP, bPH):
	hT = 0
	for bICP in bIP:
		bICPAE = bICP
		temp = bICPAE // bPH
		if bICPAE % bPH != 0:
			temp = temp + 1
		hT = hT + temp
	return hT
nOTC = int(input())
for _ in range(0, nOTC):
	(nOP, hG) = input().split()
	(nOP, hG) = (int(nOP), int(hG))
	bIP = list(map(int, input().split()))
	(st, end) = (1, max(bIP))
	ans = -1
	while st <= end:
		bPH = (st + end) // 2
		hT = trace(bIP, bPH)
		if hT > hG:
			st = bPH + 1
		else:
			ans = bPH
			end = bPH - 1
	print(ans)


import math

def isTrue(l, n, k):
	b = 0
	for i in l:
		b = b + math.ceil(i / n)
	if b <= k:
		return True
	else:
		return False
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	f = 1
	r = max(l)
	res = 0
	while f <= r:
		n = (f + r) // 2
		if isTrue(l, n, k):
			res = n
			r = n - 1
		else:
			f = n + 1
	print(res)

def isTrue(l, n, k):
	b = 0
	for i in range(l):
		b = b + i / n
	if b < k:
		return True
	else:
		return False


def check(m):
	count = 0
	for el in arr:
		if m < el:
			count += (el + m - 1) // m
		else:
			count += 1
	if count <= hours:
		return True
	else:
		return False
t = int(input())
for i in range(t):
	(length, hours) = map(int, input().split())
	arr = list(map(int, input().split()))
	r = 1000000000
	l = 1
	ans = 10000000000
	while r >= l:
		m = (l + r) // 2
		if check(m):
			r = m - 1
			ans = min(ans, m)
		else:
			l = m + 1
	print(ans)


from math import ceil
T = int(input())
for a in range(T):
	(N, H) = map(int, input().split())
	A = list(map(int, input().split()))
	x = 1
	y = 10 ** 9
	hr = 0
	k = 10000000000
	while x <= y:
		b = x + (y - x) // 2
		hr = 0
		for i in range(N):
			hr += ceil(A[i] / b)
		if hr <= H:
			k = min(k, b)
			y = b - 1
		else:
			x = b + 1
	print(k)


from math import ceil

def sum_arr(arr, k):
	su = 0
	for elem in arr:
		su += ceil(elem / k)
	return su
t = int(input())
for _ in range(t):
	(n, h) = tuple(map(int, input().split()))
	a = list(map(int, input().split()))
	(b, e) = (0, max(a))
	ans = 0
	while b <= e:
		mid = (b + e) // 2
		if sum_arr(a, mid + 1) > h:
			b = mid + 1
			ans = mid + 1
		else:
			e = mid - 1
	print(ans + 1)


import math
for _ in range(int(input())):
	(n, hour) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	(low, h) = (1, max(l))
	while low != h:
		mid = (low + h) // 2
		count = 0
		for i in l:
			count += math.ceil(i / mid)
		if count <= hour:
			h = mid
		else:
			low = mid + 1
	print(low)


import math
t = int(input())

def ans(nums, h):

	def res(hours):
		x = 0
		for i in nums:
			x += math.ceil(i / hours)
		return x
	(low, high, res1) = (1, max(nums), float('inf'))
	if len(nums) == h:
		return high
	while low <= high:
		mid = (low + high) // 2
		ans = res(mid)
		if ans == h:
			res1 = min(mid, res1)
		if ans > h:
			low = mid + 1
		else:
			high = mid - 1
	return res1 if res1 != float('inf') else low
for _ in range(t):
	x = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	print(ans(arr, x[1]))


from math import ceil

def condition(arr, H, k):
	if k == 0:
		return False
	s = 0
	for i in range(len(arr)):
		if arr[i] <= k:
			s += 1
		else:
			s += ceil(arr[i] / k)
	return s <= H
t = int(input())
while t > 0:
	(n, H) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	h = max(arr) - 1
	l = 0
	m = (l + h) // 2
	flag = 0
	while l <= h:
		if condition(arr, H, m + 1):
			h = m - 1
			k = m
			flag = 1
			m = (h + l) // 2
		else:
			l = m + 1
			if flag == 0:
				k = m
			m = (h + l) // 2
	print(k + 1)
	t -= 1


def check(bananas, mid_val, H):
	time = 0
	for i in range(len(bananas)):
		if bananas[i] % mid_val != 0:
			time += bananas[i] // mid_val + 1
		else:
			time += bananas[i] // mid_val
	if time <= H:
		return True
	else:
		return False

def minEatingSpeed(piles, H):
	start = 1
	end = sorted(piles.copy(), reverse=True)[0]
	while start < end:
		mid = start + (end - start) // 2
		if check(piles, mid, H) == True:
			end = mid
		else:
			start = mid + 1
	return end
t = int(input())
for i in range(t):
	a = [int(i) for i in input().split()][:2]
	n = a[0]
	h = a[1]
	b = [int(i) for i in input().split()][:n]
	print(minEatingSpeed(b, h))


import math

def get_time(mid: int, arr: list):
	res = sum([math.ceil(i / mid) for i in arr])
	return res

def minimum_k(h: int, arr: list) -> int:
	lo = 1
	hi = max(arr)
	res = 0
	while lo <= hi:
		mid = (lo + hi) // 2
		val = get_time(mid, arr)
		if val > h:
			lo = mid + 1
		elif val <= h:
			hi = mid - 1
			res = mid
	return res
t = int(input())
for i in range(t):
	(n, h) = list(map(int, input().split(' ')))
	piles = list(map(int, input().split(' ')))
	print(minimum_k(h, piles))


import math

def speed(a, mid, h):
	tot = 0
	for i in a:
		tot += math.ceil(i / mid)
	if int(tot) <= h:
		return True
	return False
t = int(input())
for i in range(t):
	(n, h) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	low = 1
	high = a[n - 1]
	ans = 0
	while low <= high:
		mid = low + (high - low) // 2
		if speed(a, mid, h) == True:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


from math import ceil

def total_time(A, k):
	total = 0
	for i in range(len(A)):
		total = total + ceil(A[i] / k)
	return total

def binary_search(arr, h):
	low = 1
	high = max(arr)
	k = high + 1
	while low <= high:
		mid = (low + high) // 2
		time = total_time(arr, mid)
		if time <= h:
			k = min(mid, k)
			high = mid - 1
		else:
			low = mid + 1
	return k
T = int(input())
for i in range(T):
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(binary_search(arr, h))


import math

def compute(a, h, k):
	c = 0
	for i in a:
		c += math.ceil(i / k)
	return c <= h
t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	a = list(map(int, input().split()))
	(st, en) = (1, max(a))
	while st < en:
		mid = (st + en) // 2
		if compute(a, h, mid):
			en = mid
		else:
			st = mid + 1
	k = max(1, mid - 1)
	while not compute(a, h, k):
		k += 1
	print(k)


def binarySearch(arr, mid):
	t = 0
	for i in arr:
		t += i // mid
		if i % mid != 0:
			t += 1
	return t
t = int(input())
for _ in range(t):
	(l, tm) = map(int, input().split())
	arr = list(map(int, input().split()))
	low = 1
	high = max(arr)
	while low <= high:
		mid = (high + low) // 2
		t = binarySearch(arr, mid)
		if t <= tm:
			high = mid - 1
		else:
			low = mid + 1
	print(low)


def mineat(n, h, arr):
	from math import ceil
	(left, right) = (1, max(arr))
	while left < right:
		mid = left + (right - left) // 2
		allot = 0
		for i in range(n):
			allot += ceil(arr[i] / mid)
			if allot > h:
				break
		if allot > h:
			left = mid + 1
		elif allot <= h:
			right = mid
	return left
t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(mineat(n, h, arr))


import math

def check(arr, n, mid, H):
	hrs = 0
	for i in range(n):
		hrs += math.ceil(arr[i] / mid)
	if hrs <= H:
		return True
	return False

def bs(arr, n, H):
	low = 1
	high = max(arr)
	while high > low:
		mid = int((high + low) / 2)
		if check(arr, n, mid, H):
			high = mid
		else:
			low = mid + 1
	if check(arr, n, low, H) == False:
		low += 1
	return low
for _ in range(int(input())):
	(n, H) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = bs(arr, n, H)
	print(ans)


from math import ceil

def banana(s, b, limit):
	r = 0
	for i in s:
		r += ceil(i / b)
	if r <= limit:
		return True
	else:
		return False
T = int(input())
for i in range(T):
	(N, H) = map(int, input().split())
	s = list(map(int, input().split()))
	t = 1
	c = max(s)
	while t != c:
		b = (t + c) // 2
		if banana(s, b, H):
			c = b
		else:
			t = b + 1
	print(t)


a = int(input())
import math
while a > 0:
	(n, h) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	x = l[-1]
	m = l[n // 2]
	for k in range(1, x + 1):
		y = math.ceil(m / k)
		if y * n <= h:
			c = 0
			for i in l:
				c += math.ceil(i / k)
			if c < h:
				k -= 1
				w = 0
				for i in l:
					w += math.ceil(i / k)
				if w <= h:
					print(k)
				else:
					print(k + 1)
				break
			elif c == h:
				w = 0
				for i in l:
					w += math.ceil(i / k)
				if w == h:
					print(k)
				elif w > h:
					print(k + 1)
				break
	a -= 1


t = int(input())
while t > 0:
	t -= 1
	(n, h) = map(int, input().split())
	a = [int(x) for x in input().split()]
	s = sum(a)
	mx = max(a)
	low = 1
	high = mx
	mn = 0
	if n == h:
		print(mx)
	else:
		while low <= high:
			k = (low + high) // 2
			s = 0
			for ele in a:
				s += (ele + k - 1) // k
			if s <= h:
				high = k - 1
				mn = k
			else:
				low = k + 1
		print(mn)


from math import ceil

def min_banana_ph(arr, n, h):
	start = 1
	end = max(arr)
	mid = (start + end) // 2
	k = end + 1
	while start <= end:
		time = 0
		for i in range(n):
			time += ceil(arr[i] / mid)
		if time <= h:
			k = min(mid, k)
			end = mid - 1
		else:
			start = mid + 1
		mid = (start + end) // 2
	return k
t = int(input())
for i in range(t):
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(min_banana_ph(arr, n, h))


from math import ceil
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	a = list(map(int, input().split()))
	beg = 1
	end = max(a)
	mid = 0
	ans = -1
	while beg <= end:
		mid = (beg + end) // 2
		hrs = 0
		for i in range(n):
			hrs += ceil(a[i] / mid)
		if hrs <= h:
			ans = mid
			end = mid - 1
		else:
			beg = mid + 1
	print(ans)


def check(mid):
	total = 0
	for i in piles:
		total += (i + mid - 1) // mid
	return total <= hours

def solve(no_piles, hours, piles):
	lim_0 = 1
	end = max(piles)
	ans = end
	while lim_0 <= end:
		mid = (lim_0 + end) // 2
		if check(mid):
			ans = min(ans, mid)
			end = mid - 1
		else:
			lim_0 = mid + 1
	return ans
test_cases = int(input())
for _ in range(test_cases):
	(number_of_piles, hours) = list(map(int, input().split()))
	piles = list(map(int, input().split()))
	print(solve(number_of_piles, hours, piles))


from math import ceil

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

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

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	(n, h) = li()
	a = li()
	l = 1
	r = max(a)
	while l < r:
		m = (l + r) // 2
		k = m
		s = 0
		for i in range(n):
			s += ceil(a[i] / k)
		if s <= h:
			r = m
		else:
			l = m + 1
	print(l)


def bananas(lower, upper):
	k = (upper + lower) // 2
	if upper <= lower:
		return k
	sum = 0
	for i in l:
		if i % k == 0:
			sum += i / k
		else:
			sum += i // k + 1
	if sum > hours:
		return bananas(k + 1, upper)
	elif sum == hours:
		return bananas(lower, k)
	else:
		return bananas(lower, k)
test = int(input())
for i in range(test):
	nandh = [int(i) for i in input().split()]
	hours = nandh[1]
	l = [int(i) for i in input().split()]
	max = l[0]
	for i in l:
		if i > max:
			max = i
	print(bananas(1, max))


import math

def check(l, n, m, h):
	s = 0
	for i in range(n):
		s += math.ceil(l[i] / m)
	if s <= h:
		return True
	return False

def snek(l, n, h):
	a = 1
	b = max(l)
	while b > a:
		c = int((b + a) / 2)
		if check(l, n, c, h):
			b = c
		else:
			a = c + 1
	if check(l, n, a, h) == False:
		a += 1
	return a
t = int(input())
for i in range(t):
	(n, h) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = snek(l, n, h)
	print(ans)


from math import ceil

def is_possible(a, val, h):
	ct = 0
	for elem in a:
		ct += ceil(elem / val)
	return ct <= h

def soln(n, h, a):
	ssum = sum(a)
	mmin = ceil(ssum / h)
	mmax = max(a)
	while mmin <= mmax:
		mid = (mmin + mmax) // 2
		if is_possible(a, mid, h):
			mmax = mid - 1
		else:
			mmin = mid + 1
	return mmin

def main():
	t = int(input())
	while t:
		(n, h) = [int(i) for i in input().split()]
		a = [int(i) for i in input().split()]
		ans = soln(n, h, a)
		print(ans)
		t -= 1
main()


from math import ceil

def works(array, value, limit):
	p = 0
	for i in array:
		p += ceil(i / value)
	if p <= limit:
		return True
	else:
		return False
for _ in range(int(input())):
	(N, H) = map(int, input().split())
	array = list(map(int, input().split()))
	low = 1
	high = max(array)
	while low != high:
		middle = (low + high) // 2
		if works(array, middle, H):
			high = middle
		else:
			low = middle + 1
	print(low)


from math import ceil

def check(b, n, p, lim):
	ans = 0
	for i in b:
		ans += ceil(i / p)
	if ans <= lim:
		return True
	else:
		return False
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = max(a)
	(l, r) = (1, p)
	while l != r:
		m = (l + r) // 2
		if check(a, n, m, k):
			r = m
		else:
			l = m + 1
	print(r)


from math import ceil as top

def check(mid):
	res = 0
	for i in arr:
		res += top(i / mid)
	if res <= h:
		return True
	return False
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	low = 1
	high = max(arr)
	while low <= high:
		mid = (low + high) // 2
		if check(mid):
			high = mid - 1
		else:
			low = mid + 1
	print(low)


for z in range(int(input())):
	(n, h) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]

	def bs(l, r, h):
		if l > r:
			return max(a)
		m = int((l + r) / 2)
		x = 0
		for i in range(len(a)):
			x += 1 + a[i] // m
			if a[i] % m == 0:
				x -= 1
		if x <= h:
			return min(bs(l, m - 1, h), m)
		return bs(m + 1, r, h)
	print(bs(1, max(a), h))


import math

def solve(arr, n):
	s = 0
	for i in arr:
		s += math.ceil(i / n)
	return s

def BS(arr, n, hr, mx):
	l = 1
	h = mx
	while l <= h:
		mid = (l + h) // 2
		n = solve(arr, mid)
		if n <= hr:
			res = mid
			h = mid - 1
		else:
			l = mid + 1
	return res
for t in range(int(input())):
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	mx = max(arr)
	print(BS(arr, n, h, mx))


import math
t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	l = list(map(int, input().split()))
	mini = 1
	maxi = max(l)
	k_now = -1
	flag = True
	mid = -1
	while mini < maxi:
		cost = 0
		mid = (mini + maxi) // 2
		for i in l:
			cost += math.ceil(i / mid)
		if cost <= h:
			k_now = mid
			maxi = mid
		else:
			mini = mid + 1
	print(max(mini, mid))


from math import ceil

def bin(arr, h):

	def func(arr, v, h):
		c = 0
		for i in range(len(arr)):
			c = c + ceil(arr[i] / v)
		if c <= h:
			return True
		else:
			return False
	low = 1
	high = max(arr)
	k = high + 1
	while low <= high:
		mid = (low + high) // 2
		if func(arr, mid, h) == True:
			k = min(mid, k)
			high = mid - 1
		else:
			low = mid + 1
	return k
n = int(input())
inputs = []
for i in range(n):
	(l, h) = map(int, input().split())
	read = list(map(int, input().split()))
	inputs.append([read, l, h])
for i in range(n):
	print(bin(inputs[i][0], inputs[i][2]))