Given an array A[] of N integers, where A[i] denotes the height of i^{th} tree. 
Geek needs to cut down M meters of wood. He has a woodcutting machine that works as follows:  Set the blade at a height parameter H, and the machine cuts off all trees having a height greater than H. The trees having less than height H remains intact.
Since Geek is an environmentalist, he doesn't want to cut woods more than necessary, so he set the height H as high as possible.
Find the maximum height H of the blade that still allows to cutoff at least M meters of wood.
Example 1:
Input:
A[] = {20, 15, 10, 17}
M = 7
Output: 15
Explanation: 
Set the height parameter to 15, then Geek can chop:
  1.5 metres from first tree
  2. 0 metres from second tree
  3. 0 metres from third tree
  4. 2 metres from fourth tree
  So in total Geek chopped 5 + 2 = 7 metres of wood.
Example 2:
Input:
A[] = {4, 42, 40, 26, 46}
M = 20
Output: 36
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxHeight() which takes an array and an integer and returns an integer as output.
Expected Time Complexity: O(N *logN)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{6}
1 <= A[i] <=10^{6}
1 <= B <=2 * 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: from typing import List





class Solution:

    def maxHeight(self, N : int, A : List[int], M : int) -> int:

        # code here

        



Solutions:
from typing import List

def check(mid, arr, M):
	for ele in arr:
		M -= max(0, ele - mid)
		if M <= 0:
			return True
	return False

class Solution:

	def maxHeight(self, N: int, A: List[int], M: int) -> int:
		mx = 0
		mn = 0
		for ele in A:
			mx = max(mx, ele)
		while mn <= mx:
			mid = (mn + mx) // 2
			if check(mid, A, M):
				mn = mid + 1
			else:
				mx = mid - 1
		return mx


from typing import List
import math

class Solution:

	def maxHeight(self, N: int, A: List[int], M: int) -> int:
		if M <= 0:
			return max(A)
		A.sort(reverse=True)
		H = A[0]
		for i in range(1, N):
			cut = (H - A[i]) * i
			if M > cut:
				M -= cut
				H = A[i]
			else:
				H -= math.ceil(M / i)
				return H
		return 0


from typing import List

class Solution:

	def maxHeight(self, N: int, A: List[int], M: int) -> int:
		A.sort(reverse=True)

		def check(n):
			c = 0
			for i in A:
				if i >= n:
					c += i - n
					if c >= M:
						return True
				else:
					return False
			return c >= M
		low = 0
		high = A[0]
		while low <= high:
			mid = (low + high) // 2
			if check(mid):
				low = mid + 1
			else:
				high = mid - 1
		return high


from typing import List

class Solution:

	def check(self, arr, m, h):
		cut = 0
		for x in arr:
			if x > h:
				cut += x - h
		return cut >= m

	def maxHeight(self, N: int, A: List[int], M: int) -> int:
		(l, r) = (0, max(A))
		ans = -1
		while l <= r:
			mid = l + r >> 1
			if self.check(A, M, mid):
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans


from typing import List

class Solution:

	def maxHeight(self, N: int, A: List[int], M: int) -> int:
		(i, j) = (min(A), max(A))
		ans = -1
		while i <= j:
			m = (i + j) // 2
			if max_m(A, m) >= M:
				ans = m
				i = m + 1
			else:
				j = m - 1
		return ans

def max_m(A, h):
	ans = 0
	for a in A:
		if a > h:
			ans += a - h
	return ans


from typing import List

class Solution:

	def maxHeight(self, N: int, A: List[int], M: int) -> int:

		def ispos(mid, A, M):
			for i in A:
				if i > mid:
					M -= i - mid
			if M <= 0:
				return True
			return False
		high = max(A)
		low = min(A)
		ans = low
		while low <= high:
			mid = (low + high) // 2
			if ispos(mid, A, M):
				ans = mid
				low = mid + 1
			else:
				high = mid - 1
		return ans


from typing import List

class Solution:

	def binary(self, start, end, arr, curCount, count, M):
		ans = start
		temp1 = end
		while start <= end:
			mid = start + (end - start) // 2
			temp = count * (temp1 - mid)
			if curCount + temp >= M:
				ans = mid
				start = mid + 1
			else:
				end = mid - 1
		return ans

	def maxHeight(self, n: int, arr: List[int], M: int) -> int:
		arr.sort(reverse=True)
		curCount = 0
		arr.append(0)
		for i in range(1, n + 1):
			temp = i * (arr[i - 1] - arr[i])
			if curCount + temp >= M:
				return self.binary(arr[i], arr[i - 1], arr, curCount, i, M)
			curCount += temp
		return -1


from typing import List

class Solution:

	def maxHeight(self, N: int, A: List[int], M: int) -> int:
		A.sort()
		low = 0
		high = max(A)
		res = -1
		while low <= high:
			mid = (low + high) // 2
			sum1 = 0
			for i in range(N):
				if A[i] > mid:
					sum1 = sum1 + (A[i] - mid)
				if sum1 >= M:
					break
			if sum1 >= M:
				res = mid
				low = mid + 1
			else:
				high = mid - 1
		return res


from typing import List

class Solution:

	def maxHeight(self, n: int, x: List[int], M: int) -> int:

		def check(e):
			i = 0
			j = n - 1
			ans = -1
			while i <= j:
				m = (i + j) // 2
				if x[m] >= e:
					ans = m
					j = m - 1
				else:
					i = m + 1
			if ans == -1:
				return False
			return p[-1] - p[ans] - e * (n - ans) >= M
		x.sort()
		p = [0]
		for i in x:
			p.append(p[-1] + i)
		i = 0
		j = x[-1]
		ans = 0
		while i <= j:
			m = (i + j) // 2
			if check(m):
				ans = m
				i = m + 1
			else:
				j = m - 1
		return ans


from typing import List

class Solution:

	def maxHeight(self, N: int, A: List[int], M: int) -> int:
		mx = max(A)
		if M <= 0:
			return mx
		A.sort(reverse=True)

		def isSufficient(val):
			sm = 0
			for i in range(N):
				temp = A[i] - val
				if temp <= 0:
					break
				sm += temp
			if sm >= M and sm - i < M:
				return M
			return sm

		def solve(start, end):
			while start <= end:
				mid = start + (end - start) // 2
				val = isSufficient(mid)
				if val == M:
					return mid
				elif val < M:
					end = mid - 1
				else:
					start = mid + 1
			return 0
		return solve(0, mx)

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = IntArray().Input(N)
		M = int(input())
		obj = Solution()
		res = obj.maxHeight(N, A, M)
		print(res)


from typing import List

class Solution:

	def getWood(self, treesHeight, height):
		totalWood = 0
		for treeHeight in treesHeight:
			if treeHeight > height:
				totalWood += treeHeight - height
		return totalWood

	def solve(self, treesHeight, requiredWood):
		(lowestHeight, highestHeight) = (0, max(treesHeight))
		minimumHeightNeeded = 0
		while lowestHeight <= highestHeight:
			mid = (lowestHeight + highestHeight) // 2
			gotWood = self.getWood(treesHeight, mid)
			if gotWood == requiredWood:
				return mid
			elif gotWood > requiredWood:
				minimumHeightNeeded = mid
				lowestHeight = mid + 1
			else:
				highestHeight = mid - 1
		return minimumHeightNeeded

	def maxHeight(self, N: int, A: List[int], M: int) -> int:
		return self.solve(A, M)

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = IntArray().Input(N)
		M = int(input())
		obj = Solution()
		res = obj.maxHeight(N, A, M)
		print(res)