Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Daanish as always is busy creating and solving his favourite and interesting graph problems. Chef assigns each problem a difficulty — an integer between $1$ and $10$. For each valid $i$, there are $A_{i}$ problems with difficulty $i$.

A participant hacked Daanish's account and got access to the problem proposal document. He can delete up to $K$ problems from the document in order to reduce the difficulty of the contest for himself and his friends. Find the smallest possible value of the difficulty of the most difficult problem which remains after removing $K$ problems.

------  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 $10$ space-separated integers $A_{1}, A_{2}, \ldots, A_{10}$.
The second line contains a single integer $K$.

------  Output ------
For each test case, print a single line containing one integer — the minimum difficulty of the most difficult remaining problem.

------  Constraints ------
$1 ≤ T ≤ 2 \cdot 10^{4}$
$0 ≤ A_{i} ≤ 10^{8}$ for each valid $i$
$A_{1} + A_{2} + \ldots + A_{10} > 0$
$0 ≤ K < A_{1} + A_{2} + \ldots + A_{10}$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
5

1 10 1 5 3 2 4 9 0 100

100

2 0 1 0 0 0 0 0 0 10

12

2 0 1 0 0 0 0 10 0 0

0

2 0 1 0 0 0 0 0 0 10

10

1 10 1 5 3 2 4 9 0 100

125
----- Sample Output 1 ------ 
8

1

8

3

2
----- explanation 1 ------ 
Example case 1: The participant can remove all $100$ problems with difficulty $10$. Then, there are no problems with difficulties $9$ and $10$, so the maximum difficulty among remaining problems is $8$.

Example case 2: The participant can remove all problems with difficulties $3$ and $10$ and any one of the problems with difficulty $1$. Then, the only problem left has difficulty $1$.

Example case 3: The participant cannot remove any problem. The document does not contain any problems with difficulties $9$ or $10$, so the maximum difficulty of a problem is $8$.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for t in range(int(input())):
	problems = [int(x) for x in input().split()]
	delete = int(input())
	i = 9
	while i > -1:
		if problems[i] > delete:
			print(i + 1)
			break
		else:
			delete -= problems[i]
		i -= 1


def problem(A, K):
	diff_level = 10
	while K >= A[diff_level - 1]:
		K -= A[diff_level - 1]
		diff_level -= 1
	return diff_level
for i in range(int(input())):
	lst = list(map(int, input().split()))
	k = int(input())
	print(problem(lst, k))


t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	k = int(input())
	while k != 0:
		i = len(l)
		if l[i - 1] > k:
			k = 0
		elif l[i - 1] == 0:
			l.pop(i - 1)
		else:
			k = k - l[i - 1]
			l.pop(i - 1)
	for i in range(len(l) - 1, -1, -1):
		if l[i] == 0:
			l.pop(i)
		else:
			break
	print(len(l))


for i in range(int(input())):
	lst = list(map(int, input().split()))
	k = int(input())
	res = 10
	for i in range(10):
		if k < lst[9 - i]:
			print(res)
			break
		k -= lst[9 - i]
		res -= 1


for i in range(int(input())):
	lst = list(map(int, input().split()))
	k = int(input())
	i = 9
	ans = -1
	while k >= lst[i]:
		k -= lst[i]
		lst[i] = 0
		i -= 1
	for i in range(10):
		if lst[i]:
			ans = i + 1
	print(ans)


for _ in range(int(input())):
	a = [int(x) for x in input().split()]
	k = int(input())
	i = 9
	while i and k:
		if a[i]:
			x = min(a[i], k)
			a[i] -= x
			k -= x
		i -= 1
	i = 9
	while i and (not a[i]):
		i -= 1
	print(i + 1)


for t in range(int(input())):
	ai = [int(i) for i in input().split()]
	n = int(input())
	l = 9
	while n > 0 and 9 > 0 or ai[l] == 0:
		n -= ai[l]
		if n > -1:
			l -= 1
		else:
			break
	print(l + 1)


t = int(input())
while t > 0:
	arr = list(map(int, input().split()))
	k = int(input())
	l = len(arr)
	for i in range(l - 1, -1, -1):
		if arr[i] > 0 and arr[i] <= k:
			k = k - arr[i]
			arr[i] = 0
		elif arr[i] > 0 and arr[i] > k and (k != 0):
			arr[i] = arr[i] - k
			k = 0
		if k == 0:
			break
	ind = 0
	for j in range(l - 1, -1, -1):
		if arr[j] > 0:
			ind = j + 1
			break
	print(ind)
	t = t - 1


t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	k = int(input())
	for i in range(9, -1, -1):
		if sum(a[i:]) > k:
			print(i + 1)
			break


for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	s = 0
	f = 0
	for i in range(len(a) - 1, -1, -1):
		s += a[i]
		if s == k:
			break
		if s > k:
			f = 1
			print(i + 1)
			break
	if f == 1:
		continue
	for j in range(i - 1, -1, -1):
		if a[j] != 0:
			print(j + 1)
			break


t = int(input())
for i in range(t):
	arr = list(map(int, input().split()))
	K = int(input())
	i = 9
	while i >= 0:
		K = K - arr[i]
		if K >= 0:
			i = i - 1
		else:
			break
	print(i + 1)


test_cases = int(input())
for t in range(test_cases):
	problems = input().split()
	for i in range(len(problems)):
		problems[i] = int(problems[i])
	remove = int(input())
	i = 9
	while remove > 0:
		remove -= problems[i]
		if remove < 0:
			i = i + 1
		i = i - 1
	while problems[i] == 0:
		i = i - 1
	print(i + 1)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	m = []
	for i in a[::-1]:
		m.append(k - i)
		k -= i
	m = m[::-1]
	for i in range(9, -1, -1):
		if m[i] < 0:
			print(i + 1)
			break


T = int(input())
for _ in range(0, T):
	a = list(map(int, input().split()))
	k = int(input())
	a = a[::-1]
	for i in range(0, len(a)):
		if a[i] <= k:
			k -= a[i]
			a[i] = 0
		else:
			k = 0
			print(len(a) - i)
			break


for x in range(int(input())):
	l = list(map(int, input().split()))
	k = int(input())
	i = -1
	for y in range(len(l) - 1, -1, -1):
		if l[y] <= k and k != 0 and (l[y] != 0):
			k = k - l[y]
			l[y] = 0
		elif k < l[y] and k != 0 and (l[y] != 0):
			l[y] = l[y] - k
			k = 0
		if k == 0:
			break
	for y in range(len(l)):
		if l[y] != 0:
			i = y
	print(i + 1)


for t in range(int(input())):
	a = [int(x) for x in input().split()]
	k = int(input())
	s = sum(a) - k
	c = 0
	for i in range(10):
		c += a[i]
		if c >= s:
			print(i + 1)
			break


for _ in range(int(input())):
	x = list(map(int, input().split()))
	y = int(input())
	total = 0
	mini = 10
	for i in range(len(x) - 1, -1, -1):
		total += x[i]
		if total <= y:
			mini = min(mini, i)
		else:
			break
	print(mini)


for t in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	n = len(a)
	for i in range(1, n + 1):
		if k < a[-i]:
			a[-i] = a[-i] - k
			k = 0
			break
		else:
			k = k - a[-i]
			a[-i] = 0
			n -= 1
	print(n)


n = int(input())
for i in range(n):
	lst = [int(i) for i in input().split(' ')][:10]
	k = int(input())
	lst = lst[::-1]
	x = 0
	for i in range(len(lst)):
		x += lst[i]
		if i == 9:
			print(1)
			break
		elif k < x:
			print(10 - i)
			break
		elif x == k and lst[i + 1] != 0:
			print(9 - i)
			break
		else:
			continue


for _ in range(int(input())):
	l = list(map(int, input().split()))
	n = int(input())
	sum = 0
	l.reverse()
	for i in range(10):
		if n - sum >= l[i]:
			sum += l[i]
			l[i] = 0
		else:
			l[i] = l[i] - (n - sum)
			sum += n - sum
			break
	for k in l:
		if k != 0:
			print(10 - i)
			break


for _ in range(int(input())):
	l = list(map(int, input().split()))
	k = int(input())
	i = 9
	while k != 0 and i > -1:
		if l[i] == 0:
			i = i - 1
			continue
		if l[i] > k:
			k = 0
			break
		elif l[i] == k:
			l[i] = 0
			k = 0
			break
		else:
			k = k - l[i]
			l[i] = 0
		i = i - 1
	for i in range(9, -1, -1):
		if l[i] != 0:
			print(i + 1)
			break


t = input()
for c in range(0, int(t)):
	a = input().split()
	arr = []
	for x in a:
		arr.append(int(x))
	k = int(input())
	counter = 10
	for x in range(9, -1, -1):
		temp = arr[x]
		arr[x] = arr[x] - k
		if arr[x] < 0:
			arr[x] == 0
		k = k - temp
		if k <= 0:
			break
		else:
			counter = counter - 1
	start = counter - 1
	for y in range(start, -1, -1):
		if arr[y] == 0:
			counter = counter - 1
		else:
			break
	print(counter)


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


for _ in range(int(input())):
	c = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
	l = list(map(int, input().split()))
	k = int(input())
	i = 9
	while i > -1 and k >= 0:
		if k >= l[i]:
			c[i] = 0
			k -= l[i]
			i -= 1
		else:
			break
	for i in range(10):
		if c[i] == 1:
			k = i
	print(k + 1)


for _ in range(int(input())):
	arr = list(map(int, input().split()))
	k = int(input())
	for i in reversed(range(10)):
		k -= arr[i]
		if k < 0:
			print(i + 1)
			break


for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	for i in range(9, -1, -1):
		if a[i] > k:
			print(i + 1)
			break
		else:
			k -= a[i]


for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	c = 9
	while k >= a[c]:
		k = k - a[c]
		c = c - 1
	print(c + 1)


for i in range(int(input())):
	l = list(map(int, input().split()))
	k = int(input())
	c = 9
	while k >= l[c]:
		k = k - l[c]
		c = c - 1
	print(c + 1)


for i in range(int(input())):
	li = list(map(int, input().split()))
	k = int(input())
	d = {}
	for i in range(1, 11):
		d[i] = li[i - 1]
	i = 10
	while k > 0 or d[i] == 0:
		if d[i] <= 0:
			i -= 1
		elif k - d[i] < 0:
			k = k - d[i]
		else:
			k = k - d[i]
			i -= 1
	print(i)


for _ in range(int(input())):
	A = list(map(int, input().split()))
	k = int(input())
	for j in range(9, -1, -1):
		if A[j] > k:
			print(j + 1)
			break
		else:
			k -= A[j]


t = int(input())
for _ in range(t):
	a = list(map(int, input().split()))
	k = int(input())
	b = sum(a) - k
	s = 0
	for i in range(10):
		if b > s:
			s += a[i]
		if b <= s:
			print(i + 1)
			break


T = int(input())
for i in range(0, T):
	a = input().split()
	bb = 0
	for j in range(0, 10):
		a[j] = int(a[j])
		bb += a[j]
	k = int(input())
	bb = bb - k
	ss = 0
	for j in range(0, 10):
		if bb > ss:
			ss += a[j]
		if bb <= ss:
			print(j + 1)
			break


for _ in range(int(input())):
	l = list(map(int, input().split()))
	k = int(input())
	for i in range(len(l)):
		l[i] = (i + 1) * l[i]
	for i in range(len(l) - 1, -1, -1):
		temp = l[i]
		l[i] = max(0, l[i] - k * (i + 1))
		k = max(0, k - temp // (i + 1))
		if k == 0:
			break
	for j in range(len(l) - 1, -1, -1):
		if l[j] != 0:
			print(j + 1)
			break


for _ in range(int(input())):
	li = list(map(int, input().split()))
	k = int(input())
	while k - li[-1] >= 0:
		k = k - li[-1]
		li.pop(-1)
	print(len(li))


tests = int(input())
for i in range(tests):
	arr = list(map(int, input().split()))
	k = int(input())
	ans = -1
	for j in range(9, -1, -1):
		if k >= arr[j]:
			k -= arr[j]
			arr[j] = 0
		if arr[j] > 0:
			ans = j + 1
			break
	print(ans)


for j in range(int(input())):
	l = list(map(int, input().split()))
	k = int(input())
	c = 0
	m = 0
	for i in range(9, -1, -1):
		if c <= k:
			c += l[i]
		if c > k:
			break
	print(i + 1)


for _ in range(int(input())):
	a = [int(i) for i in input().split()]
	k = int(input())
	while k > 0:
		for i in range(len(a) - 1, -1, -1):
			if a[i] == 0:
				pass
			elif k - a[i] >= 0:
				k = k - a[i]
				a[i] = 0
			else:
				a[i] = a[i] - k
				k = 0
	for i in range(len(a) - 1, -1, -1):
		if a[i] == 0:
			pass
		else:
			print(i + 1)
			break


for t in range(int(input())):
	a = list(map(int, input().split()))
	x = 9
	k = int(input())
	for i in reversed(range(x + 1)):
		y = k
		if k > 0:
			if a[i] > 0:
				k = y - a[i]
				a[i] = a[i] - y
		else:
			break
	for i in reversed(range(x + 1)):
		if a[i] > 0:
			print(i + 1)
			break


for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	s = k
	for i in reversed(range(10)):
		if a[i] <= k:
			k = k - a[i]
		elif a[i] > k:
			break
	print(i + 1)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	s = 0
	i = 9
	while s <= k:
		s += a[i]
		i -= 1
	print(i + 2)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	c = 0
	p = 9
	while c <= k:
		c += a[p]
		p -= 1
	print(p + 2)


for _ in range(int(input())):
	arr = list(map(int, input().split()))
	k = int(input())
	a = k
	while a > 0:
		for i in range(len(arr) - 1, -1, -1):
			a = k - arr[i]
			arr[i] = arr[i] - k
			k = a
			if a <= 0:
				break
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] > 0:
			print(i + 1)
			break


T = int(input())
for i in range(T):
	arr = list(map(int, input().split(' ')))
	k = int(input())
	for i in range(9, -1, -1):
		if arr[i] <= k:
			k -= arr[i]
		elif arr[i] > k:
			break
	print(i + 1)


for _ in range(int(input())):
	diff = list(map(int, input().split()))
	k = int(input())
	ans = 10
	while k != 0:
		if diff[ans - 1] >= k:
			diff[ans - 1] -= k
			k = 0
		else:
			k -= diff[ans - 1]
			diff[ans - 1] = 0
			ans -= 1
	while diff[ans - 1] == 0:
		ans -= 1
	print(ans)


for _ in range(int(input())):
	arr = list(map(int, input().split()))
	n = int(input())
	for i in range(len(arr) - 1, -1, -1):
		c = min(arr[i], n)
		arr[i] -= c
		n -= c
	c = 0
	for i in range(len(arr)):
		if arr[i] != 0:
			c = i + 1
	print(c)


t = int(input())
for _ in range(t):
	lst = [int(x) for x in input().split()]
	k = int(input())
	i = len(lst) - 1
	while i > 0:
		k -= lst[i]
		if k < 0:
			break
		i -= 1
	print(i + 1)


t = int(input())
for i in range(t):
	a = list(map(int, input().split(' ')))
	k = int(input())
	l = 9
	while k > 0 and l > -1:
		if k < a[l]:
			break
		k -= a[l]
		a[l] = 0
		l -= 1
	l = 0
	max = 0
	for j in a:
		if j != 0:
			max = l
		l += 1
	print(max + 1)


tests = int(input())
for _ in range(tests):
	problems = [int(problem) for problem in input().split(' ')]
	max_del = int(input())
	difficulty = 10
	for problem in problems[::-1]:
		difficulty -= 1
		max_del -= problem
		if max_del < 0:
			print(difficulty + 1)
			break
	else:
		print(1)


for tc in range(int(input())):
	A = list(map(int, input().split()))
	K = int(input())
	i = 9
	Curr = K
	while Curr > 0 or A[i] == 0:
		Curr = Curr - A[i]
		if Curr < 0:
			break
		if i > 0:
			i += -1
	print(i + 1)


for _ in range(int(input())):
	A = list(map(int, input().split()))
	k = int(input())
	i = 9
	level = -1
	while i >= 0:
		if k - A[i] == 0:
			k = 0
			i -= 1
			continue
		elif k - A[i] < 0:
			level = i
			break
		else:
			k = k - A[i]
			i -= 1
	print(level + 1)


t = int(input())
for _ in range(t):
	l = [int(x) for x in input().split()]
	k = int(input())
	i = len(l) - 1
	while i > 0:
		if l[i] > k:
			break
		elif l[i] == 0:
			i -= 1
		else:
			k -= l[i]
			i -= 1
	print(i + 1)


for _ in range(int(input())):
	arr = [i for i in map(int, input().split())]
	k = int(input())
	i = 9
	while i >= 0:
		if arr[i] > k:
			arr[i] -= k
			k = 0
			break
		else:
			k -= arr[i]
			arr[i] = 0
		if arr[i] == 0 or k > 0:
			i -= 1
		else:
			break
	print(i + 1)


t = int(input())
while t:
	t -= 1
	a = [int(x) for x in input().split()]
	k = int(input())
	index = 10
	for i in range(9, -1, -1):
		k -= a[i]
		if k < 0:
			print(i + 1)
			break


t = int(input())
for i in range(t):
	dif = list(map(int, input().split()))
	k = int(input())
	for j in range(9, -1, -1):
		k -= dif[j]
		if k < 0:
			print(1 + j)
			break


for _ in range(int(input())):
	p = list(map(int, input().split()))
	k = int(input())
	p.insert(0, 0)
	for i in range(1, len(p)):
		if p[-i] > k:
			p[-i] -= k
			if p[-i] > 0:
				maxi = len(p) - i
				break
		else:
			k -= p[-i]
			p[-i] = 0
	print(maxi)


for _ in range(int(input())):
	arr = list(map(int, input().split()))
	k = int(input())
	arr1 = [sum(arr)]
	for i in range(1, 10):
		arr1.append(sum(arr[i:]))
	i = 9
	while arr1[i] <= k:
		i -= 1
	print(i + 1)


t = int(input())
for o in range(t):
	arr = [k for k in map(int, input().split())]
	k = int(input())
	if k == 0:
		for i in range(9, -1, -1):
			if arr[i] != 0:
				ans = i + 1
				break
	else:
		for i in range(9, -1, -1):
			if k >= arr[i]:
				k = k - arr[i]
			else:
				ans = i + 1
				break
	print(ans)


for _ in range(int(input())):
	arr = list(map(int, input().split()))
	k = int(input())
	n = len(arr)
	for i in range(n - 1, -1, -1):
		if arr[i] > k and arr[i] != 0:
			print(i + 1)
			break
		if arr[i] <= k:
			k -= arr[i]


for _ in range(int(input())):
	prob = list(map(int, input().split()))
	k = int(input())
	prob.reverse()
	for (i, j) in enumerate(prob):
		k -= j
		if k < 0:
			print(10 - i)
			break


for _ in range(int(input())):
	lst = [int(x) for x in input().split()]
	n = int(input())
	rlst = []
	rlst = lst[::-1]
	i = int(0)
	j = 0
	count = 0
	while n > 0:
		if rlst[i] <= n:
			n -= rlst[i]
			rlst[i] = 0
			i += 1
		else:
			n = 0
	while rlst[j] == 0:
		count += 1
		j += 1
	print(10 - count)


t = int(input())
while t > 0:
	l = list(map(int, input().split()))
	k = int(input())
	for i in range(9, -1, -1):
		if l[i] != 0:
			k = l[i] - k
			if k <= 0:
				k = -k
			else:
				p = i
				break
	print(p + 1)
	t -= 1


for t in range(int(input())):
	a = list(map(int, input().split()))
	k = int(input())
	i = 10
	while sum(a[i - 1:10]) <= k:
		i -= 1
	print(i)


for _ in range(int(input())):
	q = list(map(int, input().split()))
	k = int(input())
	total = 0
	for i in range(9, -1, -1):
		total += q[i]
		if total > k:
			print(i + 1)
			break
	else:
		print(0)


t = int(input())
ans = []
for i in range(t):
	a = list(map(int, input().split()))
	a = a[::-1]
	k = int(input())
	i = 0
	while i < len(a):
		if k == 0:
			break
		if a[i] != 0:
			c = min(a[i], k)
			a[i] = a[i] - c
			k = k - c
			if k == 0:
				break
		i += 1
	a = a[::-1]
	for i in range(len(a) - 1, -1, -1):
		if a[i] != 0:
			print(i + 1)
			break


for _ in range(int(input())):
	k = list(map(int, input().split()))
	d = int(input())
	for j in range(9, -1, -1):
		if k[j] > 0:
			d = d - k[j]
			if d < 0:
				print(j + 1)
				break


T = int(input())
for tc in range(T):
	l = list(map(int, input().split(' ')))
	k = int(input())
	for i in range(9, -1, -1):
		if k >= l[i]:
			k = k - l[i]
		else:
			print(i + 1)
			break


for t in range(int(input())):
	a = list(map(int, input().split()))
	b = int(input())
	c = 9
	while b >= a[c]:
		b = b - a[c]
		c = c - 1
	print(c + 1)


for _ in range(int(input())):
	l = list(map(int, input().split()))
	n = int(input())
	for i in range(len(l) - 1, -1, -1):
		if l[i] > n and l[i] != 0:
			print(i + 1)
			break
		else:
			n -= l[i]


for j in range(int(input())):
	l = list(map(int, input().split()))
	k = int(input())
	i = len(l) - 1
	while k > 0:
		if l[i] >= k:
			l[i] -= k
			k = 0
			break
		elif l[i] < k:
			k -= l[i]
			l[i] = 0
			i -= 1
	while l[i] == 0:
		i -= 1
	print(i + 1)