You are given N toys in a shop .
The cost of each toy is represented by an array A[]. You are given Q queries, For ith query, You have a C amount of money which you can use to purchase the toys. Also there are K broken toys and you won't purchase them. The task is to calculate the maximum number of toys you can purchase using the C amount of money.
Note: 1 based indexing is used. Each query is treated independently. 
Query definition: The first element represents an integer C where C=Queries[i][0].
The second element represents an integer K, where K = Queries[i][1].
The next K integers represent the indices of broken toys which are Queries[i][j] ,j>1
Example 1:
Input:
N = 5
A[] = {8, 6, 9, 2, 5}
Q = 2
Query[][] = {{12,2,3,4},{30,0}}
Output:
2 5
Explanation:
Query 1: C = 12, K = 2 , 
Indices of Broken toys is {3,4}
Indices of Available toys are {1,2,5}
If we purchase the toys 2 and 5 , 
then cost = A[2]+A[5]= 6+5 = 11,
Therefore,We purchase the 2 toys 
using 11 amount of money.
Query 2: C = 30, K = 0
There is no broken toy. 
We can purchase all toys,
cost = A[1]+A[2]+A[3]+A[4]+A[5]= 30
Therefore,We purchase the 5 toys
using 30 amount of money.
Example 2:
Input:
N = 2
A[] = {3,3}
Q = 1
Query[][] = {{1,0}}
Output:
0
Explanation:
Query 1: C = 1, K = 0 , 
There is no broken toy. 
We have not enough amount to purchase 
any toy.
Your Task: 
You don't need to read input or print anything. Your task is to complete the function maximumToys() which takes the integer N and array A[ ],  integer Q and 2D array Queries[][] as input parameters and returns the array of answers of each query.
Expected Time Complexity: O(NLogMx + Q*K*LogMx + Q*(LogMx)^{2})
Expected Auxiliary Space: O(Mx)
Where Mx is the maximum element present in the array A[i].
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{6}
1 ≤ Q ≤ 10^{4}
1 ≤ C ≤ 10^{9}
0 ≤ K ≤ 10
1 ≤ Queries[i][j] ≤ N, j>1

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def maximumToys(self,N,A,Q,Queries):

      #code here

  

Solutions:
class Solution:

	def maximumToys(self, N, A, Q, Queries):
		toys = sorted(((item, i + 1) for (i, item) in enumerate(A)))
		output = []
		for item in Queries:
			banned = set(item[2:])
			money = item[0]
			count = 0
			for (cost, toy) in toys:
				if cost > money:
					break
				if not toy in banned:
					money -= cost
					count += 1
			output.append(count)
		return output


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		arr = [(A[i], i) for i in range(N)]
		arr.sort()
		mp = {arr[i][1]: i for i in range(N)}
		prefix = [0] * (N + 1)
		prefix[0] = 0
		for i in range(1, N + 1):
			prefix[i] = prefix[i - 1] + arr[i - 1][0]
		res = []
		for i in range(Q):
			c = Queries[i][0]
			k = Queries[i][1]
			l = 0
			r = N
			ans = 0
			while l <= r:
				mid = l + (r - l) // 2
				if prefix[mid] <= c:
					ans = mid
					l = mid + 1
				else:
					r = mid - 1
			if ans <= 0:
				res.append(0)
				continue
			idx = ans - 1
			rem = c - prefix[ans]
			notRemoved = set()
			for j in range(k):
				qIdx = mp[Queries[i][j + 2] - 1]
				if qIdx <= idx:
					ans -= 1
					rem += arr[qIdx][0]
				else:
					notRemoved.add(qIdx)
			s = idx + 1
			while s < N and arr[s][0] <= rem:
				if s not in notRemoved:
					ans += 1
					rem -= arr[s][0]
				s += 1
			res.append(ans)
		return res


class Solution:

	def fun(self, arr, amount, k, broken):
		(n, toys, temp) = (len(arr), 0, [])
		for i in range(1, n + 1):
			if arr[i - 1][0] not in broken:
				if amount >= arr[i - 1][1]:
					temp.append(arr[i - 1][1])
					amount -= arr[i - 1][1]
					toys += 1
				else:
					return toys
		return toys

	def maximumToys(self, n, arr, q, queries):
		ans = []
		brr = []
		for (i, ele) in enumerate(arr):
			brr.append((i + 1, ele))
		brr.sort(key=lambda x: x[1])
		for i in range(q):
			amount = queries[i][0]
			k = queries[i][1]
			if len(queries[i]) > 2:
				broken = queries[i][2:]
			else:
				broken = []
			broken = set(broken)
			ans.append(self.fun(brr, amount, k, broken))
		return ans


from collections import Counter

class Fenwick:

	def __init__(self, n):
		self.tree = [0] * n
		self.F = lambda x: x & x + 1
		self.H = lambda x: x | x + 1

	def update(self, ind, delta):
		while ind < len(self.tree):
			self.tree[ind] += delta
			ind = self.H(ind)

	def query(self, ind):
		res = 0
		while ind >= 0:
			res += self.tree[ind]
			ind = self.F(ind) - 1
		return res

class Solution:

	def maximumToys(self, n, A, Q, Queries):
		mx = max(A)
		counter = Counter(A)
		(count, csum) = (Fenwick(mx + 1), Fenwick(mx + 1))
		for a in A:
			count.update(a, 1)
			csum.update(a, a)
		res = []
		for q in Queries:
			c = q[0]
			for b in q[2:]:
				count.update(A[b - 1], -1)
				csum.update(A[b - 1], -A[b - 1])
			(lo, hi) = (0, mx)
			while lo < hi:
				mid = lo + (hi - lo + 1) // 2
				if csum.query(mid) > c:
					hi = mid - 1
				else:
					lo = mid
			res.append(count.query(lo) + min((c - csum.query(lo)) // (lo + 1), counter[lo + 1]))
			for b in q[2:]:
				count.update(A[b - 1], 1)
				csum.update(A[b - 1], A[b - 1])
		return res


from bisect import bisect_right

class Solution:

	def maximumToys(self, N, A, Q, Queries):
		toys = [(toyPrice, i + 1) for (i, toyPrice) in enumerate(A)]
		toys.sort()
		prefixs = []
		_sum = 0
		for (toyPrice, _) in toys:
			_sum += toyPrice
			prefixs.append(_sum)
		res = []
		for q in Queries:
			(c, k) = q[:2]
			i = bisect_right(prefixs, c)
			if i == 0:
				res.append(0)
				continue
			not_contained = 0
			cnt = 0
			for j in range(i):
				if toys[j][1] in q[2:]:
					not_contained += toys[j][0]
				else:
					cnt += 1
			while i < N:
				if toys[i][1] in q[2:]:
					not_contained += toys[i][0]
					i += 1
					continue
				amount = prefixs[i] - not_contained
				if c < amount:
					break
				else:
					i += 1
					cnt += 1
			res.append(cnt)
		return res


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		ans = []
		sorted_arr = []
		for (i, val) in enumerate(A):
			sorted_arr.append((val, i))
		sorted_arr.sort()

		def dp(money_left):
			toys = 0
			for i in range(N):
				if sorted_arr[i][1] not in broken:
					if money_left >= sorted_arr[i][0]:
						toys += 1
						money_left -= sorted_arr[i][0]
					else:
						return toys
			return toys
		for query in Queries:
			if query[1] > 0:
				broken = set((x - 1 for x in query[2:]))
			else:
				broken = set()
			ans.append(dp(query[0]))
		return ans


class Solution:

	def maximumToys(self, n, arr, q, queries):
		res = []
		for i in range(n):
			res.append([arr[i], i + 1])
		res.sort()
		ans = []
		for item in queries:
			c = item[0]
			k = item[1]
			num = set()
			if k > 0:
				num = set(item[2:].copy())
			cc = 0
			for x in res:
				val = x[0]
				ind = x[1]
				if ind not in num and c - val >= 0:
					cc += 1
					c -= val
			ans.append(cc)
		return ans


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		ans = []
		for i in range(len(A)):
			A[i] = (A[i], i + 1)
		A.sort()
		for i in range(len(Queries)):
			amount = Queries[i][0]
			map = {}
			if Queries[i][1] > 0:
				for j in range(2, len(Queries[i])):
					map[Queries[i][j]] = 1
			count = 0
			for toy in range(len(A)):
				if A[toy][1] not in map:
					if amount > 0 and A[toy][0] <= amount:
						count += 1
						amount -= A[toy][0]
					else:
						break
			ans.append(count)
		return ans


n = 10 ** 6 + 5
fr = [0] * n

class tree:

	def __init__(self) -> None:
		self.bit = [0] * n

	def add(self, node, v):
		while node < n:
			self.bit[node] += v
			node += node & -node

	def get(self, node):
		sumt = 0
		while node > 0:
			sumt += self.bit[node]
			node -= node & -node
		return sumt
(t1, t2) = (tree(), tree())

class Solution:

	def maximumToys(self, n, A, Q, Queries):
		new = []
		for i in A:
			fr[i] += 1
		for i in A:
			t1.add(i, i)
			t2.add(i, 1)
		for i in Queries:
			C = i[0]
			for j in range(2, len(i)):
				t1.add(A[i[j] - 1], -A[i[j] - 1])
				t2.add(A[i[j] - 1], -1)
			(lw, hg) = (1, 10 ** 6)
			pos = 10 ** 6
			while lw <= hg:
				mid = (lw + hg) // 2
				if t1.get(mid) >= C:
					pos = mid
					hg = mid - 1
				else:
					lw = mid + 1
			ans = t2.get(pos - 1)
			mx = min((C - t1.get(pos - 1)) // pos, fr[pos])
			ans += mx
			new.append(ans)
			for j in range(2, len(i)):
				t1.add(A[i[j] - 1], A[i[j] - 1])
				t2.add(A[i[j] - 1], 1)
		for i in range(len(A)):
			t1.add(A[i], -A[i])
			t2.add(A[i], -1)
			fr[A[i]] -= 1
		return new


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		answer = list()
		for query in Queries:
			temp = A.copy()
			coin = query[0]
			brokens = list()
			for i in range(query[1]):
				brokens.append(query[i + 2])
			for broken in brokens:
				temp.remove(A[broken - 1])
			temp.sort()
			buy = 0
			fee = 0
			for i in range(len(temp)):
				fee += temp[i]
				if fee > coin:
					break
				else:
					buy += 1
			answer.append(buy)
		return answer


class Solution:

	def maximumToys(self, N, A, nq, Q):
		d = {}
		l = set()
		for i in range(N):
			if A[i] not in d:
				d[A[i]] = 1
			else:
				d[A[i]] += 1
			l.add(A[i])
		ans = []
		l = list(l)
		l.sort()
		for q in range(nq):
			amt = Q[q][0]
			b = Q[q][1]
			m = d.copy()
			for j in range(b):
				m[A[Q[q][2 + j] - 1]] -= 1
			toy = 0
			for ele in l:
				if amt >= ele:
					add = min(amt // ele, m[ele])
					amt -= add * ele
					toy += add
				elif amt < ele:
					break
			ans += [toy]
		return ans


from bisect import bisect_right

class Solution:

	def maximumToys(self, N, A, Q, Queries):
		arr = [(A[i], i) for i in range(N)]
		arr.sort()
		new = [0] * N
		for i in range(N):
			new[arr[i][1]] = i
		sort_arr = []
		s = 0
		res = []
		for i in range(N):
			s += arr[i][0]
			sort_arr.append(s)
		for q in Queries:
			(c, n) = (q[0], q[1])
			idx = bisect_right(sort_arr, c)
			ans = idx
			if idx > 0:
				c -= sort_arr[idx - 1]
			else:
				res.append(0)
				continue
			broken = set(q[2:])
			for e in broken:
				if new[e - 1] < idx:
					ans -= 1
					c += A[e - 1]
			i = idx
			while i < N:
				if c - arr[i][0] >= 0:
					if arr[i][1] + 1 not in broken:
						c -= arr[i][0]
						ans += 1
					i += 1
				else:
					break
			res.append(ans)
		return res


class Solution:

	def binarysearch(self, arr, n, k):
		l = 0
		r = n - 1
		lp = -1
		while l <= r:
			m = (l + r) // 2
			if arr[m] <= k:
				lp = l
				l = m + 1
			elif arr[m] > k:
				r = m - 1
		return lp

	def maximumToys(self, N, A, Q, Queries):
		arr = []
		res = [0] * Q
		for i in range(N):
			arr.append([A[i], i])
		arr.sort()
		parr = [0] * N
		oldNewIndexMap = {}
		parr[0] = arr[0][0]
		oldNewIndexMap[arr[0][1]] = 0
		for i in range(1, N):
			parr[i] = parr[i - 1] + arr[i][0]
			oldNewIndexMap[arr[i][1]] = i
		for qi in range(Q):
			c = Queries[qi][0]
			k = Queries[qi][1]
			broken = set()
			indx = self.binarysearch(parr, N, c)
			val = indx + 1
			leftAmt = c - parr[indx]
			for j in range(k):
				newIndex = oldNewIndexMap[Queries[qi][2 + j] - 1]
				if newIndex <= indx:
					val -= 1
					leftAmt += arr[newIndex][0]
				else:
					broken.add(newIndex)
			for ni in range(indx + 1, N):
				if ni not in broken:
					if leftAmt >= arr[ni][0]:
						leftAmt -= arr[ni][0]
						val += 1
					else:
						break
			res[qi] = val
		return res


from functools import cmp_to_key

class Solution:

	def compare(self, item1, item2):
		return item1[0] - item2[0]

	def maximumToys(self, N, A, Q, Queries):
		Ai = []
		i = 0
		for a in A:
			Ai.append((a, i + 1))
			i += 1
		Ais = sorted(Ai, key=cmp_to_key(self.compare))
		output = []
		for q in Queries:
			amount = q[0]
			k = q[1]
			broken = set(q[2:])
			counter = 0
			money_left = True
			for toy in Ais:
				if not money_left:
					break
				if toy[1] not in broken:
					if amount >= toy[0]:
						counter += 1
						amount -= toy[0]
					else:
						money_left = False
			output.append(counter)
		return output


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		tot = []
		for q in Queries:
			amt = q[0]
			ans = 0
			cnt = 0
			cost = list(A)
			l = len(q)
			for i in range(2, l):
				cost.remove(A[q[i] - 1])
			cost.sort()
			for i in cost:
				ans += i
				cnt += 1
				if ans > amt:
					ans -= i
					cnt -= 1
					break
			tot.append(cnt)
		return tot


class Solution:

	def countToys(self, arr, cntuse, money):
		count = 0
		for (cost, idx) in arr:
			if cost > money:
				break
			if idx + 1 not in cntuse:
				money -= cost
				count += 1
		return count

	def maximumToys(self, N, A, Q, Queries):
		arr = [(A[i], i) for i in range(N)]
		arr.sort(key=lambda x: x[0])
		res = []
		for query in Queries:
			money = query[0]
			cntuse = set(query[2:])
			ans = self.countToys(arr, cntuse, money)
			res.append(ans)
		return res


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		arr = []
		for (i, num) in enumerate(A, 1):
			arr.append((num, i))
		arr.sort()
		res = []
		for num in Queries:
			c = num[0]
			s = set([])
			count = 0
			if num[1]:
				s = set(num[2:])
			for item in arr:
				if item[1] not in s:
					if c >= item[0]:
						count += 1
						c -= item[0]
					else:
						break
			res.append(count)
		return res


from collections import defaultdict

class Solution:

	def maximumToys(self, N, A, Q, Queries):
		price_cntr = defaultdict(int)
		for p in A:
			price_cntr[p] += 1
		unique_price = list(set(price_cntr.keys()))
		unique_price.sort()
		ans = []
		for qi in range(Q):
			qry = Queries[qi]
			C = qry[0]
			K = qry[1]
			restricted_price_cntr = defaultdict(int)
			for i in qry[2:]:
				restricted_price_cntr[A[i - 1]] += 1
			ans.append(0)
			for price in unique_price:
				available_toys = price_cntr[price] - restricted_price_cntr[price]
				if available_toys * price <= C:
					ans[-1] += available_toys
					C -= available_toys * price
				elif price <= C:
					can_buy = C // price
					ans[-1] += can_buy
					C -= can_buy * price
				else:
					break
		return ans


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		ans = list()
		l = A.copy()
		l.sort()
		d1 = dict()
		for i in range(N):
			if l[i] in d1.keys():
				d1[l[i]].append(i)
			else:
				d1[l[i]] = list()
				d1[l[i]].append(i)
		otn = dict()
		for i in range(N):
			otn[i] = d1[A[i]][-1]
			d1[A[i]].pop()
		for i in Queries:
			l = A.copy()
			money = i[0]
			sm = 0
			totaltoys = 0
			rst = set()
			if i[1] != 0:
				for j in i[2:]:
					rst.add(otn[j - 1])
			l.sort()
			for j in range(N):
				if j not in rst:
					sm += l[j]
					if sm > money:
						break
					totaltoys += 1
			ans.append(totaltoys)
		return ans


class Solution:

	def fun(self, A, amount, k, broken):
		(N, toys, temp) = (len(A), 0, [])
		for i in range(1, N + 1):
			if A[i - 1][0] not in broken:
				if amount >= A[i - 1][1]:
					temp.append(A[i - 1][1])
					amount -= A[i - 1][1]
					toys += 1
				else:
					return toys
		return toys

	def maximumToys(self, N, A, Q, Queries):
		ans = []
		brr = []
		for (i, ele) in enumerate(A):
			brr.append((i + 1, ele))
		brr.sort(key=lambda x: x[1])
		for i in range(Q):
			amount = Queries[i][0]
			k = Queries[i][1]
			if len(Queries[i]) > 2:
				broken = Queries[i][2:]
			else:
				broken = []
			broken = set(broken)
			ans.append(self.fun(brr, amount, k, broken))
		return ans


class Solution:

	def maximumToys(self, n, arr, q, queries):
		ans = []
		for query in queries:
			(C, K, broken_indices) = (query[0], query[1], set(query[2:]))
			available_indices = set(range(1, n + 1)) - broken_indices
			available_toys = [arr[i - 1] for i in available_indices]
			available_toys.sort()
			(total_cost, count) = (0, 0)
			for cost in available_toys:
				if total_cost + cost <= C:
					total_cost += cost
					count += 1
				else:
					break
			ans.append(count)
		return ans


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		cc = []
		for zz in range(Q):
			AA = list(A)
			c = Queries[zz][0]
			k = Queries[zz][1]
			if k:
				for _ in Queries[zz][2:]:
					AA[_ - 1] = -1
			z = 0
			cc.append(0)
			AA.sort()
			for _ in AA:
				if _ < 0:
					continue
				if z + _ <= c:
					z += _
					cc[zz] += 1
				else:
					break
		return cc


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		ans = []
		for i in range(Q):
			temp = A.copy()
			added = 0
			totToys = 0
			(money, broke) = (Queries[i][0], Queries[i][1])
			if broke != 0:
				for j in Queries[i][2:broke + 2]:
					temp.remove(A[j - 1])
			sortedToys = sorted(temp)
			added = sum(sortedToys)
			totToys = len(sortedToys)
			if added <= money:
				ans.append(totToys)
			else:
				while added > money:
					try:
						added -= sortedToys.pop()
						totToys -= 1
					except:
						totToys = 0
						break
				ans.append(totToys)
		return ans


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		output = []
		sa = []
		for i in range(N):
			sa.append((A[i], i + 1))
		sa.sort()
		for i in range(Q):
			broke = Queries[i][2:]
			money = Queries[i][0]
			count = 0
			for val in sa:
				if val[0] > money:
					break
				if val[1] not in broke:
					money = money - val[0]
					count += 1
			output.append(count)
		return output


class Solution:

	def maximumToys(self, N, A, Q, Queries):

		def cost(x):
			sum = 0
			count = 0
			x.sort()
			for i in x:
				if sum + i <= C:
					sum = sum + i
					count += 1
			return count
		ans = []
		for i in range(Q):
			C = Queries[i][0]
			K = Queries[i][1]
			x = A.copy()
			if K == 0:
				count = cost(x)
				ans.append(count)
			else:
				for j in range(2, 2 + K):
					x.remove(A[Queries[i][j] - 1])
				count = cost(x)
				ans.append(count)
		return ans


from itertools import accumulate

class Solution:

	def maximumToys(self, N, A, Q, Queries):

		def _count_consecutive():
			Con = [1] * N
			c = 1
			for i in range(1, N):
				if S[i] != S[i - 1]:
					c = 1
					continue
				c += 1
				Con[i] = c
			return Con

		def _calc_cost(m):
			sum_cost = Acc[m]
			Concnt = Con[m]
			mv = S[m]
			skip_cnt = same_val_cnt = 0
			for skip in skips:
				if skip < mv:
					sum_cost -= skip
					skip_cnt += 1
				elif skip == mv and same_val_cnt < Concnt:
					sum_cost -= skip
					skip_cnt += 1
					same_val_cnt += 1
				else:
					break
			return (sum_cost, skip_cnt)
		S = sorted(A)
		Con = _count_consecutive()
		Acc = list(accumulate(S))
		ans = []
		for q in Queries:
			(C, skips) = (q[0], sorted([A[i - 1] for i in q[2:]]))
			(L, R, skip_cnt) = (0, N - 1, 0)
			while L <= R:
				m = (L + R) // 2
				(v, skip_cnt) = _calc_cost(m)
				if v <= C:
					L = m + 1
				elif v > C:
					R = m - 1
			ans.append(R + 1 - skip_cnt)
		return ans


import bisect

class Solution:

	def maximumToys(self, N, A, Q, Queries):
		price = sorted([(x, i) for (i, x) in enumerate(A)], key=lambda x: x[0])
		idx = [0] * N
		for i in range(N):
			idx[price[i][1]] = i
		sums = [0] * N
		sums[0] = price[0][0]
		for i in range(1, N):
			sums[i] = sums[i - 1] + price[i][0]
		ans = []
		for q in Queries:
			C = q[0]
			K = q[1]
			bought_blocked = 0
			blocked = sorted(q[2:], key=lambda x: idx[x - 1])
			for a in blocked:
				pos = idx[a - 1]
				if sums[pos] <= C + A[a - 1]:
					C += A[a - 1]
					bought_blocked += 1
				else:
					break
			pos = bisect.bisect_left(sums, C)
			if pos < N and sums[pos] == C:
				pos += 1
			ans.append(pos - bought_blocked)
		return ans


import copy

class Solution:

	def maximumToys(self, N, A, Q, Queries):
		ans = [-1] * Q
		for i in range(Q):
			__A = copy.copy(A)
			C = Queries[i][0]
			B = Queries[i][1]
			if B > 0:
				if B >= N:
					ans[i] = 0
					continue
				for j in range(B):
					idx = Queries[i][j + 2] - 1
					__A[idx] = 0
			__A.sort()
			j = 0
			while j < len(__A) and __A[j] == 0:
				j += 1
			__s = 0
			for k in range(j, len(__A)):
				if __s + __A[k] >= C:
					if __s + __A[k] == C:
						ans[i] = k + 1 - j
					else:
						ans[i] = k - j
					break
				else:
					__s += __A[k]
			if ans[i] == -1:
				ans[i] = k - j + 1
		return ans


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		res = []
		for q in Queries:
			toy = A.copy()
			amount = q[0]
			brk = q[1]
			if brk == N:
				res.append(0)
				continue
			if brk > 0:
				for i in q[2:]:
					toy[i - 1] = -1
			toy.sort()
			(cnt, till) = (0, 0)
			for (key, j) in enumerate(toy):
				if j != -1:
					till += j
					if till < amount:
						cnt += 1
						if key == N - 1:
							res.append(cnt)
							break
					elif till > amount:
						res.append(cnt)
						break
					else:
						res.append(cnt + 1)
						break
		return res


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		(req_map, dupli_A) = self.give_dupli(A)
		f_tree2 = [i for i in range(N + 1)]
		f_tree1 = [0]
		for i in dupli_A:
			f_tree1.append(f_tree1[-1] + i)
		self.reconstruct_ftree(f_tree1)
		self.reconstruct_ftree(f_tree2)
		res = []
		for Query in Queries:
			C = Query[0]
			self.get_all_update(Query, f_tree1, f_tree2, req_map, A, -1)
			indx = self.binary_search(f_tree1, C) - 1
			res.append(self.sum(f_tree2, indx))
			self.get_all_update(Query, f_tree1, f_tree2, req_map, A, 1)
		return res

	def reconstruct_ftree(self, arr):
		for i in range(len(arr) - 1, 0, -1):
			arr[i] -= arr[i - (i & -i)]

	def sum(self, arr, indx):
		res = 0
		while indx > 0:
			res += arr[indx]
			indx -= indx & -indx
		return res

	def get_all_update(self, arr, tree1, tree2, req_map, A, val):
		for i in range(2, len(arr)):
			self.update(tree1, req_map[arr[i]], A[arr[i] - 1] * val)
			self.update(tree2, req_map[arr[i]], val)

	def update(self, arr, indx, val):
		while indx < len(arr):
			arr[indx] += val
			indx += indx & -indx

	def give_dupli(self, A):
		a = sorted([(num, i + 1) for (i, num) in enumerate(A)], key=lambda t: t[0])
		req_map = {}
		for i in range(len(a)):
			req_map[a[i][1]] = i + 1
		a = [i[0] for i in a]
		yield req_map
		yield a

	def binary_search(self, f_tree, val):
		(l, r) = (0, len(f_tree))
		while l + 1 < r:
			mid = (l + r) // 2
			if self.sum(f_tree, mid) > val:
				r = mid
			else:
				l = mid
		return r


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		a = sorted([(A[i], i + 1) for i in range(len(A))])
		ans = []
		for i in range(len(Queries)):
			(C, k) = (Queries[i][0], Queries[i][1])
			bid = set()
			toy = 0
			for j in range(2, len(Queries[i])):
				bid.add(Queries[i][j])
			for j in range(len(a)):
				(c, p) = (a[j][0], a[j][1])
				if p not in bid and C >= c:
					C -= c
					toy += 1
			ans.append(toy)
		return ans


from bisect import bisect_left
from itertools import accumulate

def solve(arr, c, l):
	a = [val for (i, val) in enumerate(arr) if i + 1 not in l]
	a.sort()
	p = list(accumulate(a))
	if not p:
		return 0
	ind = bisect_left(p, c)
	if ind == 0 and p and (p[0] > c):
		return 0
	elif ind == len(a):
		return ind
	elif p[ind] == c:
		return ind + 1
	else:
		return ind

class Solution:

	def maximumToys(self, N, A, Q, Queries):
		res = []
		for arr in Queries:
			(c, k, l) = (arr[0], arr[1], set(arr[2:]))
			res.append(solve(A, c, l))
		return res


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		ans = []
		for q in Queries:
			c = q[0]
			k = q[1]
			arr = A.copy()
			if k > 0:
				for i in range(2, k + 2):
					arr[q[i] - 1] = -1 * arr[q[i] - 1]
			arr.sort()
			toy = 0
			i = 0
			while i < len(arr) and c >= arr[i]:
				if arr[i] > 0:
					toy += 1
					c = c - arr[i]
				i += 1
			ans.append(toy)
		return ans


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		sortedArr = [[x, idx] for (idx, x) in enumerate(A)]
		sortedArr.sort()
		ans = []
		for query in Queries:
			C = query[0]
			K = query[1]
			brokenIndices = set()
			for i in range(2, len(query)):
				brokenIndices.add(query[i] - 1)
			canBuy = 0
			for i in range(N):
				if sortedArr[i][1] in brokenIndices:
					continue
				if C < sortedArr[i][0]:
					break
				C -= sortedArr[i][0]
				canBuy += 1
			ans.append(canBuy)
		return ans


class Node:

	def __init__(self, index, value):
		self.index = index
		self.value = value

class Solution:

	def maximumToys(self, N, A, Q, Queries):
		self.base = [Node(i, A[i]) for i in range(N)]
		self.base.sort(key=lambda x: x.value)
		queryResults = [0] * Q
		i = 0
		for query in Queries:
			(budget, brokenCount) = (query[0], query[1])
			if query[1] == 0:
				broken = {}
			else:
				broken = {x: 1 for x in query[2:]}
			maxToys = self.getToys(budget, broken)
			queryResults[i] = maxToys
			i += 1
		return queryResults

	def getToys(self, budget, broken):
		summ = 0
		count = 0
		for node in self.base:
			if node.index + 1 in broken:
				broken.pop(node.index + 1)
			else:
				newsumm = summ + node.value
				if newsumm > budget:
					return count
				summ = newsumm
				count += 1
		return count


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		count = []
		for q in Queries:
			x = 0
			c = q[0]
			a1 = A[:]
			if q[1] > 0:
				broken = sorted(q[2:], reverse=True)
				for ele in broken:
					del a1[ele - 1]
			a1.sort()
			result = 0
			if c >= sum(a1):
				x += len(a1)
			else:
				for (i, element) in enumerate(a1):
					result += element
					if c >= result:
						x += 1
					else:
						break
			count.append(x)
		return count


class Solution:

	def maximumToys(self, N, A, Q, Queries):
		result = []
		for i in range(Q):
			C = Queries[i][0]
			K = Queries[i][1]
			arr = A.copy()
			for j in Queries[i][2:]:
				arr[j - 1] = 0
			count = 0
			sum = 0
			arr.sort()
			for i in range(0, N, 1):
				if sum + arr[i] <= C and arr[i] > 0:
					sum = sum + arr[i]
					count += 1
			result.append(count)
		return result


import sys

class Solution:

	def Sort(self, A):
		arr = A.sort()
		return arr

	def maximumToys(self, N, A, Q, Queries):
		res = [0] * Q
		for i in range(Q):
			cost = Queries[i][0]
			temp = A.copy()
			zero = 0
			for j in range(Queries[i][1]):
				n = Queries[i][j + 2] - 1
				temp[n] = 0
			temp = sorted(temp)
			summ = 0
			count = 0
			for m in range(N - 1, -1, -1):
				if temp[m] <= cost:
					flag = m
					break
			for k in range(zero, flag + 1):
				if temp[k] > cost:
					break
				summ += temp[k]
				if temp[k] > 0 and summ <= cost:
					count += 1
				if summ > cost:
					break
			res[i] = count
		return res


import sys

class Solution:

	def Sort(self, A):
		arr = A.sort()
		return arr

	def maximumToys(self, N, A, Q, Queries):
		res = [0] * Q
		listt = sorted(A)
		for i in range(Q):
			temp = listt.copy()
			cost = Queries[i][0]
			for j in range(Queries[i][1]):
				temp.remove(A[Queries[i][j + 2] - 1])
			summ = 0
			count = 0
			for j in range(N - Queries[i][1]):
				summ += temp[j]
				if summ <= cost:
					count += 1
			res[i] = count
		return res


import bisect
import sys

class Solution:

	def maximumToys(self, N, A, Q, Queries):
		lis = []
		ind = dict()
		for (i, j) in enumerate(A):
			lis.append([j, i])
		lis.sort()
		for i in range(N):
			ind[lis[i][1]] = i
		prefix = [0]
		for i in range(1, N + 1):
			prefix.append(prefix[-1] + lis[i - 1][0])
		prefix.append(sys.maxsize)
		res = []
		for i in Queries:
			c = i[0]
			k = i[1]
			ans = 0
			low = 0
			high = N
			while low <= high:
				mid = (low + high) // 2
				if prefix[mid] <= c:
					ans = mid
					low = mid + 1
				else:
					high = mid - 1
			rem = c - prefix[ans]
			if ans <= 0:
				res.append(0)
				continue
			idx = ans - 1
			s = set()
			for j in range(k):
				qInd = ind[i[j + 2] - 1]
				if qInd <= idx:
					ans -= 1
					rem += lis[qInd][0]
				else:
					s.add(qInd)
			idx = idx + 1
			while idx < N and lis[idx][0] <= rem:
				if idx not in s:
					ans += 1
					rem -= lis[idx][0]
				idx += 1
			res.append(ans)
		return res