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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
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)

# cook your dish here
import math
T = int(input())
for _ in range(T):
 N, H = map(int, input().split())
 A = list(map(int, input().split()))
 low = 1
 high = 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)

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

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

# cook your dish here
import math
T = int(input())
for _ in range(T):
 N, H = map(int, input().split())
 A = list(map(int, input().split()))
 A.sort()
 low = 1
 high = max(A)
 ans = 1
 while low <= high:
  time = 0
  mid = low + (high - low) // 2
  for i in range(N):
   time += int((A[i] + mid - 1) / mid)
  
  if time <= H :
   ans = mid
   high = mid - 1
  else:
   low = mid + 1
 print(ans)

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=list(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)


# cook your dish here
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)
   


from math import *
for u in range(int(input())):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 x,y=1,max(l)
 while(x!=y):
  m=(x+y)//2
  s=0
  for i in l:
   s+=ceil(i/m)
  if(s<=k):
   y=m
  else:
   x=m+1
 print(x)


from math import ceil

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


from math import ceil

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


# cook your dish here
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)


# cook your dish here
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)


# cook your dish here
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)


# cook your dish here
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)


# cook your dish here
def MinimumHours(n,h,a):
 a.sort()
 j=0
 mi=0
 s=0
 c=0
 while 1:
  mi+=1
  for i in a[-1:-(n+1):-1]:
   if i%mi==0:
    s+=(i//mi)
   else:
    s+=(i//mi)+1
   if s>h:
    c=1
    break
  if c==1:
   c=0
   s=0
  else:
   return mi
 
 
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
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)

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))
 elif k>=sum(a):
  print(1)
 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


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


# cook your dish here
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 = 10000000000000000
 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)

# cook your dish here
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)

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)

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