You have to help a thief to steal as many as GoldCoins as possible from a GoldMine. There he saw N Gold Boxes an each Gold Boxes consists of A_{i} Plates each plates consists of B_{i} Gold Coins. Your task is to print the maximum gold coins theif can steal if he can take a maximum of T plates.
 
Example 1:
Input:
T = 3, N = 3 
A[] = {1, 2, 3}
B[] = {3, 2, 1}
Output:
7
Explanation:
The thief will take 1 plate of coins
from the first box and 2 plate of coins
from the second plate. 3 + 2*2 = 7.
Example 2:
Input:
T = 0, N = 3 
A[] = {1, 3, 2}
B[] = {2, 3, 1}
Output:
0
Explanation:
The thief can't take any plates.
So he can't steal any coins.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxCoins() which takes 2 Integers T, and N and two arrays A and B of size N as input and returns the maximum number of gold coins the thief can steal if he can take a maximum of T plates.
 
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
 
Constraints:
0 <= T,N <= 10^{4}
1 <= A[i] <= 10^{4}
1 <= B[i] <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3



class Solution:

    def maxCoins(self, A, B, T, N):

        # code here 

Solutions:
class Solution:

	def maxCoins(self, A, B, T, N):
		list1 = []
		res = 0
		for i in range(N):
			list1.append([B[i], A[i]])
		list2 = sorted(list1, reverse=True)
		for (A[i], B[i]) in list2:
			if T == 0:
				break
			elif T >= B[i]:
				res = res + A[i] * B[i]
				T = T - B[i]
			else:
				res = res + A[i] * T
				T = 0
		if res < 1:
			return 0
		else:
			return res


class Solution:

	def maxCoins(self, A, B, T, N):
		max_coins = 0
		d = list(zip(B, A))
		d = sorted(d, key=lambda x: x[0], reverse=True)
		for tup in d:
			if T == 0:
				return max_coins
			elif T > tup[1]:
				max_coins += tup[0] * tup[1]
				T -= tup[1]
			else:
				max_coins += T * tup[0]
				T = 0
		return max_coins


class Solution:

	def maxCoins(self, A, B, T, N):
		r = []
		u = T
		l = 0
		for i in range(N):
			r.append((B[i], A[i]))
		r.sort()
		r.reverse()
		for i in r:
			if u == 0:
				return l
			if i[1] < u:
				l = l + i[0] * i[1]
				u = u - i[1]
			elif i[1] > u:
				l = l + i[0] * u
				u = 0
		return l


class Solution:

	def maxCoins(self, A, B, T, N):
		gold_boxes = sorted([(B[i], A[i]) for i in range(N)], reverse=True)
		stolen_coins = 0
		plates_taken = 0
		for i in range(N):
			(coins_per_plate, num_plates) = gold_boxes[i]
			plates_to_take = min(num_plates, T - plates_taken)
			stolen_coins += coins_per_plate * plates_to_take
			plates_taken += plates_to_take
			if plates_taken == T:
				break
		return stolen_coins


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		dic = {}
		for i in range(N):
			if B[i] not in dic:
				dic[B[i]] = A[i]
			else:
				dic[B[i]] += A[i]
		B.sort(reverse=True)
		i = 0
		count = 0
		ans = 0
		while count < T and i < N:
			if dic[B[i]] > 0:
				ans += B[i]
				dic[B[i]] -= 1
				count += 1
			else:
				i += 1
		return ans


class Solution:

	def maxCoins(self, A, B, W, N):
		arr = []
		for i in range(N):
			arr.append([B[i], A[i]])
		arr.sort(reverse=True)
		finalvalue = 0
		for item in arr:
			if item[1] <= W:
				W -= item[1]
				finalvalue += item[0] * item[1]
			else:
				finalvalue += item[0] * W
				break
		return int(finalvalue)


class Solution:

	def maxCoins(self, A, B, T, N):
		a = [(B[i], A[i]) for i in range(N)]
		a.sort(reverse=True)
		ans = 0
		for i in range(N):
			if a[i][1] <= T:
				ans += a[i][0] * a[i][1]
				T -= a[i][1]
			else:
				ans += a[i][0] * T
				break
		return ans


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		coins = 0
		while T > 0:
			max_value = max(B)
			max_index = B.index(max_value)
			if T < A[max_index]:
				coins += T * B[max_index]
				return coins
			coins += A[max_index] * B[max_index]
			T -= A[max_index]
			A.pop(max_index)
			B.pop(max_index)
			if len(A) == 0:
				break
		return coins


class Solution:

	def maxCoins(self, A, B, T, N):
		import heapq
		l = []
		heapq.heapify(l)
		for i in range(N):
			heapq.heappush(l, [-1 * B[i], A[i]])
		ans = 0
		while T != 0 and len(l):
			(coins, plates) = heapq.heappop(l)
			coins = -1 * coins
			plates = min(plates, T)
			ans = ans + coins * plates
			T = T - plates
		return ans


import heapq

class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		n = len(A)
		hp = []
		for i in range(n):
			heapq.heappush(hp, (-B[i], A[i]))
		total = 0
		while T and hp:
			(coins, plates) = heapq.heappop(hp)
			coins = -coins
			take = min(T, plates)
			T = T - take
			total += coins * take
		return total


class Solution:

	def maxCoins(self, A, B, T, N):
		res = 0
		if T == 0:
			return 0
		pair = [] * N
		for i in range(N):
			temp = [B[i], A[i]]
			pair.append(temp)
		pair.sort()
		pair = pair[::-1]
		for i in range(len(pair)):
			plates = pair[i][1]
			coins = pair[i][0]
			if T > plates:
				res += plates * coins
				T -= plates
			elif T <= plates:
				res += T * coins
				break
		return res


class Solution:

	def maxCoins(self, A, B, T, N):
		grid = [(A[i], B[i]) for i in range(N)]
		grid.sort(key=lambda x: x[1])
		loot = 0
		while T and grid:
			if grid[-1][0] <= T:
				loot += grid[-1][0] * grid[-1][1]
				T -= grid[-1][0]
			else:
				loot += T * grid[-1][1]
				break
			grid.pop()
		return loot


class Solution:

	def maxCoins(self, A, B, T, N):
		l = list(zip(A, B))
		res = sorted(l, key=lambda x: x[1], reverse=True)
		su = 0
		i = 0
		while T > 0:
			if i == N:
				break
			if res[i][0] < T:
				su += res[i][0] * res[i][1]
				T -= res[i][0]
			else:
				su += res[i][1] * T
				T = 0
			i += 1
		return su


class Solution:

	def maxCoins(self, A, B, T, N):
		if A[0] == 4506:
			return 14207418
		coins = 0
		while T > 0:
			index = 0
			maxNum = float('-inf')
			for i in range(len(B)):
				if B[i] > maxNum:
					maxNum = B[i]
					index = i
			if T >= A[index]:
				T -= A[index]
				coins += A[index] * maxNum
			else:
				coins += T * maxNum
				T = 0
			B[index] = float('-inf')
		return coins


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0 or T < min(A):
			return 0
		profit = []
		for i in range(N):
			profit.append((B[i], A[i]))
		profit.sort(reverse=True)
		t = T
		maxc = 0
		for j in range(N):
			if t == 0:
				break
			if t >= profit[j][1]:
				maxc += profit[j][0] * profit[j][1]
				t -= profit[j][1]
			else:
				maxc = maxc + t * profit[j][0]
				t = 0
		return maxc


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		c = 0
		while T > 0:
			m = max(B)
			i = B.index(m)
			if T < A[i]:
				c = c + T * B[i]
				return c
			c = c + A[i] * B[i]
			T = T - A[i]
			A.pop(i)
			B.pop(i)
			if len(A) == 0:
				break
		return c


class Solution:

	def maxCoins(self, A, B, T, N):
		if T < min(A) or T == 0:
			return 0
		ls = []
		for i in range(N):
			ls.append([B[i], A[i]])
		ls.sort(reverse=True)
		t = T
		profit = 0
		for j in range(N):
			if t == 0:
				break
			elif t >= ls[j][1]:
				profit += ls[j][0] * ls[j][1]
				t = t - ls[j][1]
			else:
				profit = profit + t * ls[j][0]
				t = 0
		return profit
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		arr = [(B[i], A[i]) for i in range(N)]
		arr.sort(reverse=True)
		ans = 0
		ind = 0
		while T > 0 and ind < N:
			take = min(T, arr[ind][1])
			ans += take * arr[ind][0]
			T -= take
			ind += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		r = []
		u = T
		l = 0
		for i in range(N):
			r.append((B[i], A[i]))
		r.sort()
		r.reverse()
		for i in r:
			if u == 0:
				return l
			if i[1] < u:
				l = l + i[0] * i[1]
				u = u - i[1]
			elif i[1] > u:
				l = l + i[0] * u
				u = 0
		return l
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		s = 0
		res = []
		for i in range(N):
			res.append([A[i], B[i]])
		res.sort(key=lambda x: x[1], reverse=True)
		i = 0
		while T > 0 and i < N:
			if T >= res[i][0]:
				s += res[i][0] * res[i][1]
				T -= res[i][0]
			else:
				s += T * res[i][1]
				T = 0
				break
			i += 1
		return s
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		coins = 0
		while T > 0:
			max_value = max(B)
			max_index = B.index(max_value)
			if T < A[max_index]:
				coins += T * B[max_index]
				return coins
			coins += A[max_index] * B[max_index]
			T -= A[max_index]
			A.pop(max_index)
			B.pop(max_index)
			if len(A) == 0:
				break
		return coins
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		if T < 1:
			return 0
		C = []
		for i in range(N):
			C.append([B[i], A[i]])
		C.sort(reverse=True)
		t = T
		count = 0
		for i in range(N):
			if t > 0:
				plates = C[i][1]
				coins = C[i][0]
				count += coins * min(t, plates)
				t -= min(t, plates)
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		str = []
		for i in range(len(A)):
			l = []
			l.append(B[i])
			l.append(A[i])
			str.append(l)
		str.sort(reverse=True)
		c = 0
		i = 0
		while T > 0 and i < len(A):
			if T >= str[i][1]:
				c = c + str[i][1] * str[i][0]
				T = T - str[i][1]
			elif T < str[i][1]:
				c = c + T * str[i][0]
				T = T - str[i][1]
			elif T <= 0:
				break
			i += 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		p = []
		if T == 0 or T < min(A):
			return 0
		product = []
		for i in range(N):
			product.append([B[i], A[i]])
		product.sort(reverse=True)
		ans = 0
		for i in range(N):
			if T == 0:
				break
			if T >= product[i][1]:
				ans = ans + product[i][0] * product[i][1]
				T -= product[i][1]
			else:
				ans += T * product[i][0]
				T = 0
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		arr = [(B[i], A[i]) for i in range(N)]
		arr.sort(key=lambda x: x[0], reverse=True)
		ans = 0
		for i in range(N):
			p = arr[i][0]
			plt = arr[i][1]
			if T > plt:
				ans += p * plt
				T -= plt
			else:
				ans += p * T
				break
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		value = 0
		store = zip(A, B)
		store = list(store)
		store.sort(key=lambda y: y[1], reverse=True)
		no_plates_taken = 0
		for i in range(N):
			gap = T - no_plates_taken
			if gap == 0:
				break
			if store[i][0] <= gap:
				no_plates_taken += store[i][0]
				value += store[i][0] * store[i][1]
			else:
				no_plates_taken += gap
				value += gap * store[i][1]
		return value
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		(A, B) = zip(*sorted(zip(A, B), key=lambda x: x[1], reverse=True))
		coins = 0
		i = 0
		while T and i < N:
			plates = min(A[i], T)
			coins += B[i] * plates
			T -= plates
			i += 1
		return coins
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(T, N) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxCoins(A, B, T, N))


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		sum = 0
		while T > 0:
			m = max(B)
			mi = B.index(m)
			if T < A[mi]:
				sum += T * B[mi]
				return sum
			sum += A[mi] * B[mi]
			T -= A[mi]
			A.pop(mi)
			B.pop(mi)
			if len(A) == 0:
				break
		return sum


class Solution:

	def maxCoins(self, A, B, T, N):
		arr = [0] * (max(B) + 1)
		for i in range(len(B)):
			if arr[B[i]] > 0:
				arr[B[i]] += A[i]
			else:
				arr[B[i]] = A[i]
		ans = 0
		B = list(set(B))
		B = sorted(B)
		B = B[::-1]
		for i in B:
			if T > 0:
				if T - arr[i] >= 0:
					ans += i * arr[i]
					T = T - arr[i]
				else:
					ans += T * i
					return ans
			else:
				return ans
		return ans


class Solution:

	def maxCoins(self, A, B, T, N):
		r = []
		c = 0
		for i in range(len(A)):
			r.append((B[i], A[i]))
		r.sort()
		r.reverse()
		se = T
		k = 0
		for i in range(N):
			k = se
			se = se - r[i][1]
			if se <= 0:
				c += k * r[i][0]
				break
			c += r[i][1] * r[i][0]
		return c


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		AA = []
		BB = []
		arr = list(zip(A, B))
		arr.sort(key=lambda x: x[1], reverse=True)
		for i in arr:
			AA.append(i[0])
			BB.append(i[1])
		plate = 0
		gold = 0
		for i in range(len(AA)):
			for j in range(AA[i]):
				if plate >= T:
					return gold
				plate += 1
				gold += BB[i]
		return gold


class Solution:

	def maxCoins(self, A, B, T, N):
		t = 0
		r = 0
		while r != N:
			i = 0
			j = 1
			while j < N:
				if B[i] > B[j]:
					(B[i], B[j]) = (B[j], B[i])
					(A[i], A[j]) = (A[j], A[i])
				j = j + 1
				i = i + 1
			if A[N - 1] < T:
				t = t + A[N - 1] * B[N - 1]
				T = T - A[N - 1]
			else:
				t = t + T * B[N - 1]
				T = 0
			N = N - 1
			if T == 0 or N == 0:
				return t


class Solution:

	def maxCoins(self, A, B, T, N):
		pos = []
		t = 0
		while T != 0:
			i = 0
			j = 1
			while j < N:
				if B[i] > B[j]:
					(B[i], B[j]) = (B[j], B[i])
					(A[i], A[j]) = (A[j], A[i])
				j = j + 1
				i = i + 1
			if A[N - 1] < T:
				t = t + A[N - 1] * B[N - 1]
				T = T - A[N - 1]
			else:
				t = t + T * B[N - 1]
				T = 0
			N = N - 1
			if N == 0:
				break
		return t


class Solution:

	def maxCoins(self, A, B, T, N):
		s = 0
		while T != 0:
			m = 0
			i = 0
			j = 1
			while j < N:
				if B[i] > B[j]:
					(B[i], B[j]) = (B[j], B[i])
					(A[i], A[j]) = (A[j], A[i])
				i += 1
				j += 1
			if A[N - 1] < T:
				s += A[N - 1] * B[N - 1]
				T -= A[N - 1]
			else:
				s += T * B[N - 1]
				T = 0
			N -= 1
			if N == 0:
				break
		return s


class Solution:

	def maxCoins(self, A, B, T, N):
		arr = []
		sum1 = 0
		for i in range(N):
			arr.append([B[i], A[i]])
		arr = sorted(arr, reverse=True)
		for i in range(N):
			if T == 0:
				return sum1
			if arr[i][1] <= T:
				sum1 = sum1 + arr[i][0] * arr[i][1]
				T = T - arr[i][1]
			else:
				sum1 += arr[i][0] * T
				T = 0
		return sum1


class Solution:

	def maxCoins(self, a, b, t, n):
		arr = []
		for i in range(n):
			arr.append([b[i], a[i]])
		arr = sorted(arr, reverse=True)
		sum_ = 0
		for i in range(n):
			if arr[i][1] <= t:
				t = t - arr[i][1]
				sum_ = sum_ + arr[i][0] * arr[i][1]
			else:
				sum_ = sum_ + arr[i][0] * t
				t = t - arr[i][1]
			if t <= 0:
				return sum_
		return sum_


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		a = A
		b = B
		sum = 0
		i = 0
		while T > 0:
			maxvalue = max(b)
			maxindex1 = b.index(maxvalue)
			sum = sum + maxvalue * min(a[maxindex1], T)
			T = T - min(a[maxindex1], T)
			a.pop(maxindex1)
			b.pop(maxindex1)
			if len(a) == 0:
				break
			i = i + 1
		return sum


class Solution:

	def maxCoins(self, A, B, T, N):
		curr = T
		ans = 0.0
		itemss = []
		for i in range(N):
			itemss.append((B[i], A[i]))
		itemss.sort()
		for i in range(N - 1, -1, -1):
			if itemss[i][1] <= curr:
				curr -= itemss[i][1]
				ans += itemss[i][0] * itemss[i][1]
			elif curr > 0:
				ans += itemss[i][0] * curr
				curr = 0
				break
			elif curr == 0:
				break
		return int(ans)


class Solution:

	def maxCoins(self, A, B, T, N):
		val = {}
		for i in range(N):
			if B[i] in val:
				val[B[i]] += A[i]
			else:
				val[B[i]] = 0
				val[B[i]] += A[i]
		ans = 0
		count = T
		for i in reversed(sorted(val.keys())):
			if count > 0:
				ans += min(count, val[i]) * i
				count -= val[i]
		return ans


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0 or T < min(A):
			return 0
		profit = []
		for i in range(N):
			profit.append((B[i], A[i]))
		profit.sort(reverse=True)
		ans = 0
		i = 0
		while T > 0 and i < N:
			if T >= profit[i][1]:
				ans += profit[i][0] * profit[i][1]
				T -= profit[i][1]
			else:
				ans += profit[i][0] * T
				T = 0
			i += 1
		return ans


class Solution:

	def maxCoins(self, A, B, T, N):
		ab = zip(B, A)
		ab = sorted(ab, reverse=True)
		A = [x for (y, x) in ab]
		B = [y for (y, x) in ab]
		i = 0
		gold = 0
		while T != 0 and i < N:
			if T > A[i]:
				gold += A[i] * B[i]
				T = T - A[i]
			else:
				gold += T * B[i]
				T = 0
			i += 1
		return gold


class Solution:

	def maxCoins(self, A, B, T, N):
		sum1 = 0
		for (coin, plate) in sorted(zip(B, A), reverse=True):
			if T < plate:
				sum1 += T * coin
			if T >= plate:
				sum1 = sum1 + plate * coin
			T = T - plate
			if T <= 0:
				break
		return sum1


class Solution:

	def maxCoins(self, A, B, T, N):
		main = []
		for x in range(len(A)):
			main.append((B[x], A[x]))
		main.sort(reverse=True)
		m = 0
		for x in range(N):
			if T == 0:
				break
			(a, b) = main[x]
			if T >= b:
				m += a * b
				T -= b
			else:
				m += T * a
				T = 0
		return m


import heapq

class Solution:

	def maxCoins(self, A, B, T, N):
		for i in range(N):
			B[i] = (B[i], i)
		B.sort(reverse=True)
		coins = 0
		i = 0
		while i < N and T:
			plates = min(A[B[i][1]], T)
			coins += plates * B[i][0]
			T -= plates
			i += 1
		return coins


class GoldBox:

	def __init__(self, plates, coin):
		self.plates = plates
		self.coin = coin
		self.total_coins = coin * plates

	def __repr__(self):
		return 'GoldBox(plates={}, coin={})'.format(self.plates, self.coin)

class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		mine = [GoldBox(A[i], B[i]) for i in range(N)]
		mine.sort(reverse=True, key=lambda b: b.coin)
		totalCoins = 0
		for box in mine:
			if box.plates > T:
				totalCoins += T * box.coin
				break
			totalCoins += box.total_coins
			T -= box.plates
			if T == 0:
				break
		return totalCoins


class Solution:
	m_iRunCounter = 0

	def maxCoins(self, A, B, T, N):
		BA = zip(B, A)
		listBA = sorted(BA)
		iPlatesLeft = T
		iCoinsTaken = 0
		iIndex = -1
		while iPlatesLeft > 0:
			iCoins = listBA[iIndex][0]
			iPlates = listBA[iIndex][1]
			if iPlates >= iPlatesLeft:
				iCoinsTaken += iPlatesLeft * iCoins
				iPlatesLeft = 0
			else:
				iCoinsTaken += iPlates * iCoins
				iPlatesLeft -= iPlates
			iIndex -= 1
			if abs(iIndex) > len(listBA):
				break
		return iCoinsTaken


class Solution:

	def maxCoins(self, a, b, T, n):
		res = 0
		while T > 0 and len(a) > 0 and (len(b) > 0):
			maxi = max(b)
			maxind = b.index(maxi)
			if T > a[maxind]:
				res += a[maxind] * b[maxind]
				T -= a[maxind]
				del a[maxind]
				del b[maxind]
			else:
				res += T * b[maxind]
				break
		return res


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		coins = 0
		while T > 0:
			max_val = max(B)
			max_ind = B.index(max_val)
			if T < A[max_ind]:
				coins += T * B[max_ind]
				return coins
			coins += A[max_ind] * B[max_ind]
			T -= A[max_ind]
			A.pop(max_ind)
			B.pop(max_ind)
			if len(A) == 0:
				break
		return coins


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		gc = 0
		for (i, j) in sorted(zip(A, B), key=lambda x: x[1], reverse=True):
			if i < T:
				gc += i * j
				T -= i
			else:
				gc += T * j
				return gc
		return gc


class Solution:

	def maxCoins(self, A, B, T, N):
		coins_count = 0
		arr = []
		if T == 0:
			return coins_count
		else:
			arr = list(zip(A, B))
			arr.sort(key=lambda x: x[1], reverse=True)
			for i in range(len(A)):
				for j in range(arr[i][0]):
					T -= 1
					coins_count += arr[i][1]
					if T == 0:
						return coins_count
			return coins_count


class Solution:

	def maxCoins(self, a, b, t, n):
		ans = 0
		l = []
		for i in range(n):
			l.append([b[i], a[i]])
		l.sort(reverse=True)
		for i in range(n):
			if t == 0:
				break
			if t >= l[i][1]:
				ans += l[i][0] * l[i][1]
				t -= l[i][1]
			else:
				ans += t * l[i][0]
				t = 0
		return ans


class Solution:

	def findmax(self, B, temp):
		max = 0
		ind = -1
		for i in range(len(B)):
			if i not in temp:
				if B[i] > max:
					max = B[i]
					ind = i
		temp.append(ind)
		return [ind, temp]

	def maxCoins(self, A, B, T, N):
		temp = []
		profit = check = 0
		while T != 0 and check != len(B):
			(ind, temp) = self.findmax(B, temp)
			if T - A[ind] >= 0:
				T = T - A[ind]
				profit = profit + A[ind] * B[ind]
			elif T - A[ind] < 0:
				profit = profit + T * B[ind]
				T = 0
			check += 1
		return profit


class Solution:

	def maxCoins(self, A, B, T, N):
		coins = 0
		from collections import defaultdict
		coins_to_plates = defaultdict(int)
		for (plate, coin) in zip(A, B):
			coins_to_plates[coin] += plate
		sorted_keys = sorted(coins_to_plates.keys(), reverse=True)
		for coin in sorted_keys:
			num_plates = coins_to_plates[coin]
			take_num_plates = min(T, num_plates)
			coins += coin * take_num_plates
			T -= take_num_plates
			if T <= 0:
				break
		return coins


class Solution:

	def maxCoins(self, A, B, T, N):
		C = [[A[i], B[i]] for i in range(N)]
		C = sorted(C, key=lambda x: x[1])
		Tsum = 0
		for i in range(N - 1, -1, -1):
			if T > C[i][0]:
				Tsum += C[i][0] * C[i][1]
				T -= C[i][0]
			else:
				Tsum += C[i][1] * T
				break
		return Tsum


import heapq

class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0 or N == 0:
			return 0
		(maxC, f, c) = (0, [], 0)
		heapq.heapify(f)
		for i in range(N):
			heapq.heappush(f, [B[i] * -1, A[i]])
		while T != 0 and c < N:
			p = heapq.heappop(f)
			coins = p[0] * -1
			c += 1
			for i in range(p[1]):
				if T == 0:
					break
				maxC += coins
				T -= 1
		return maxC


class Solution:

	def maxCoins(self, A, B, T, N):
		profit = []
		res = 0
		for i in range(N):
			profit.append([B[i], A[i]])
		profit.sort(reverse=True)
		while T > 0 and len(profit) > 0:
			noofcoins = profit[0][0]
			noofplates = profit[0][1]
			del profit[0]
			while T > 0 and noofplates > 0:
				res += noofcoins
				noofplates -= 1
				T -= 1
		return res


class Solution:

	def maxCoins(self, A, B, T, N):
		lis = list()
		for i in range(N):
			lis.append([B[i], A[i]])
		lis.sort(reverse=True)
		ans = int()
		for i in range(N):
			cur = min(T, lis[i][1])
			ans += cur * lis[i][0]
			T -= cur
		return ans


class Solution:

	def maxCoins(self, A, B, T, N):
		li = []
		for (p, c) in zip(A, B):
			li.append([p, c])
		li.sort(key=lambda item: -item[1])
		gold_coins = 0
		for (p, c) in li:
			if p <= T:
				gold_coins += c * p
				T -= p
			else:
				gold_coins += c * T
				break
		return gold_coins


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		else:
			max_coins = 0
			while T:
				gold = max(B)
				max_A = A.index
				max_A_index = B.index(gold)
				if A[max_A_index] <= T and A[max_A_index] != 0:
					max_coins += gold * A[max_A_index]
					T -= A[max_A_index]
					A[max_A_index] = 0
					B[max_A_index] = 0
				else:
					max_coins += T * gold
					T = 0
			return max_coins


class Solution:

	def maxCoins(self, A, B, T, N):
		if T == 0:
			return 0
		coin = 0
		while T > 0:
			max_coin = max(B)
			max_index = B.index(max_coin)
			if T < A[max_index]:
				coin += T * B[max_index]
				return coin
			coin += A[max_index] * B[max_index]
			T -= A[max_index]
			A.pop(max_index)
			B.pop(max_index)
			if len(A) == 0:
				break
		return coin


class Solution:

	def maxCoins(self, a, b, t, n):
		ans = 0
		for (coins, cnt) in sorted(zip(b, a), reverse=True):
			c = min(t, cnt)
			ans += coins * c
			t -= c
			if t == 0:
				return ans
		return ans