In a stock market, there is a product with its infinite stocks. The stock prices are given for N days, where price[i] denotes the price of the stock on the i^{th} day.
There is a rule that a customer can buy at most i stock on the i^{th} day.
If the customer has an amount of k amount of money initially. The task is to find out the maximum number of stocks a customer can buy. 
Example 1:
Input:
price[] = { 10, 7, 19 }
k = 45
Output: 4
Explanation: A customer purchases 1 stock on day 1, 
2 stocks on day 2 and 1 stock on day 3 for 
10, 7 * 2 = 14 and 19 respectively. Hence, 
total amount is 10 + 14 + 19 = 43 and number 
of stocks purchased is 4.
Example 2:
Input: 
price[] = { 7, 10, 4 }
k = 100
Output: 6
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function buyMaximumProducts() which takes an array price and an integer k and returns an integer as output.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{3}
1 <= price[i] <= 10^{3}
1 <= k <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: 



from typing import List

class Solution:

    def buyMaximumProducts(self, n : int, k : int, price : List[int]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		prices = [(val, i) for (i, val) in enumerate(price, start=1)]
		prices.sort(key=lambda x: (x[0], -x[1]))
		cnt = 0
		for (val, i) in prices:
			if i * val <= k:
				cnt += i
				k -= i * val
			else:
				temp = k // val
				k -= temp * val
				cnt += temp
			if k == 0:
				break
		return cnt


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		(price1, count, pos) = (sorted([[price[i], i + 1] for i in range(n)]), 0, 0)
		while k > 0 and pos < n:
			if k < price1[pos][0]:
				break
			elif k >= price1[pos][0] * price1[pos][1]:
				k -= price1[pos][0] * price1[pos][1]
				count += price1[pos][1]
				pos += 1
			else:
				price1[pos][1] -= 1
		return count


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = []
		for i in range(n):
			arr.append([i + 1, price[i]])
		arr.sort(key=lambda x: x[1])
		total = 0
		for i in range(n):
			p = min(arr[i][0], k // arr[i][1])
			total += p
			k -= p * arr[i][1]
		return total


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		a = []
		for i in range(n):
			a.append([price[i], i + 1])
		a.sort()
		i = 0
		c = 0
		while k > 0 and i < n:
			if a[i][1] == 0:
				i += 1
			elif a[i][0] <= k:
				c += 1
				k -= a[i][0]
				a[i][1] -= 1
			else:
				break
		return c


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		res = 0
		pair = []
		for i in range(n):
			pair.append([price[i], i + 1])
		pairs = sorted(pair, key=lambda x: x[0])
		for i in range(len(pairs)):
			price = pairs[i][0]
			stock = pairs[i][1]
			if stock * price <= k:
				res += stock
				k -= price * stock
			else:
				res += k // price
				k -= price * (k // price)
		return res


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		l = []
		for i in range(n):
			l.append([price[i], i + 1])
		ans = 0
		l.sort(key=lambda x: x[0])
		for i in range(n):
			if k >= 0:
				c = min(l[i][1], k // l[i][0])
				ans += c
				k -= l[i][0] * c
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		stocks = []
		for i in range(n):
			stocks.append((price[i], i + 1))
		stocks.sort(key=lambda x: x[0])
		curr_money = k
		ans = 0
		for i in range(n):
			if curr_money >= stocks[i][0] * stocks[i][1]:
				curr_money -= stocks[i][0] * stocks[i][1]
				ans += stocks[i][1]
			else:
				ans += curr_money // stocks[i][0]
				curr_money -= curr_money // stocks[i][0] * stocks[i][0]
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		l = []
		a = 0
		for i in range(len(price)):
			l.append([i + 1, price[i]])
		l.sort(key=lambda x: x[1])
		for i in range(n):
			res = min(l[i][0], k // l[i][1])
			a = a + res
			k = k - res * l[i][1]
		return a


from typing import List

def max_stock_i_th_day(n, k, price: []):
	price_stats = []
	for i in range(0, n):
		price_stats.append([price[i], i + 1])
	price_stats = sorted(price_stats, key=compare_by_price)
	total_spent = 0
	total_stocks = 0
	for i in range(0, n):
		price_stat = price_stats[i]
		price = price_stat[0]
		total_stock_today = price_stat[1]
		if total_spent + total_stock_today * price < k:
			total_spent = total_spent + total_stock_today * price
			total_stocks = total_stocks + total_stock_today
		else:
			money_left_spend = k - total_spent
			stocks_can_buy = money_left_spend // price
			if stocks_can_buy >= 1:
				total_spent = total_spent + stocks_can_buy * price
				total_stocks = total_stocks + stocks_can_buy
	return total_stocks

def compare_by_price(price_stat: []):
	return price_stat[0]

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		return max_stock_i_th_day(n, k, price)


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, a: List[int]) -> int:
		d = {}
		for i in range(n):
			if a[i] not in d.keys():
				d[a[i]] = i + 1
			else:
				d[a[i]] += i + 1
		ans = 0
		for i in sorted(d.keys()):
			if k <= 0:
				break
			if k / i > d[i]:
				ans += d[i]
				k -= i * d[i]
			else:
				ans += k // i
				k -= k // i * i
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		c = 0
		s = 0
		i = 0
		a = []
		count = 1
		for i in price:
			a.append([i, count])
			count += 1
		a.sort()
		for i in range(len(a)):
			c = a[i][1]
			while a[i][0] <= k and c > 0:
				s += 1
				k = k - a[i][0]
				c -= 1
		return s


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		for i in range(n):
			price[i] = [price[i], i + 1]
		price.sort()
		count = 0
		j = 0
		while j < n and k >= price[j][0]:
			x = 0
			while x < price[j][1] and k >= price[j][0]:
				k -= price[j][0]
				x += 1
			j += 1
			count += x
		return count


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		l = []
		c = 0
		m = 0
		for i in range(len(price)):
			l.append([price[i], i + 1])
		l.sort()
		for i in range(len(l)):
			d = k / l[i][0]
			if d >= l[i][1]:
				m = l[i][0] * l[i][1]
				c = c + l[i][1]
			elif d < l[i][1]:
				m = l[i][0] * int(d)
				c = c + int(d)
			k = k - m
			m = 0
			d = 0
		return c


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = []
		for i in range(n):
			arr.append([price[i], i + 1])
		arr.sort()
		count = 0
		for i in range(n):
			if arr[i][0] * arr[i][1] <= k:
				k -= arr[i][0] * arr[i][1]
				count += arr[i][1]
			else:
				count += k // arr[i][0]
				k -= k // arr[i][0] * arr[i][0]
		return count


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = [(price[i], i + 1) for i in range(n)]
		arr.sort()
		output = 0
		for (price, limit) in arr:
			if price * limit < k:
				output += limit
				k -= price * limit
			else:
				output += k // price
				break
		return output


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		for i in range(n):
			price[i] = [price[i], i + 1]
		price.sort(key=lambda x: x[0])
		i = 0
		st = 0
		while k > 0 and i < n:
			if k // price[i][0] >= price[i][1]:
				st += price[i][1]
				k -= price[i][0] * price[i][1]
				i += 1
			elif k >= price[i][0]:
				temp = k // price[i][0]
				k -= temp * price[i][0]
				st += temp
				i += 1
			else:
				break
		return st


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		c = 0
		l = len(price) - 1
		while l >= 0:
			x = price.index(min(price))
			t = x
			while k > 0 and x >= 0:
				if k <= 0 or price[t] > k:
					return c
				k = k - price[t]
				c = c + 1
				x = x - 1
			price[t] = 100000
			l = l - 1
		return c


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		P = []
		max_stocks = 0
		for i in range(n):
			P.append([price[i], i + 1])
		P.sort(key=lambda x: x[0])
		for i in range(len(P)):
			prices = P[i][0]
			stocks = P[i][1]
			if stocks * prices <= k:
				max_stocks += stocks
				k -= stocks * prices
			else:
				max_stocks += k // prices
				k -= prices * (k // prices)
		return max_stocks


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		res = []
		for x in range(n):
			res.append((x + 1, price[x]))
		res.sort(key=lambda x: x[1])
		buystocks = 0
		totalstocks = 0
		for x in range(n):
			mstocks = res[x][0]
			ammount = res[x][1]
			stocks = min(mstocks, k // ammount)
			k = k - ammount * stocks
			totalstocks += stocks
			if k <= 0:
				break
		return totalstocks


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, arr: List[int]) -> int:
		marr = [(arr[i], i) for i in range(0, n)]
		marr.sort()
		cntstocks = 0
		for item in marr:
			(ele, idx) = item
			if k == 0:
				break
			if ele * (idx + 1) <= k:
				k -= ele * (idx + 1)
				cntstocks += idx + 1
			else:
				times = k // ele
				k -= times * ele
				cntstocks += times
		return cntstocks


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		dp = []
		res = 0
		for i in range(n):
			dp.append([price[i], -i])
		dp.sort()
		for d in dp:
			d[1] *= -1
			d[1] += 1
			tmp = min(k // d[0], d[1])
			k -= tmp * d[0]
			res += tmp
			if tmp == 0:
				return res
		return res


from typing import List

class Solution:

	def solve(self, n, amount, price, dp, idx):
		if idx >= n or amount[0] <= 0:
			return 0
		if dp[idx] != -1:
			return dp[idx]
		qty = 1
		for i in range(idx):
			if price[idx] * (qty + 1) > amount[0] or qty + 1 > idx + 1:
				break
			qty += 1
		curPrice = price[idx] * qty
		exc = self.solve(n, amount, price, dp, idx + 1)
		amount[0] -= curPrice
		inc = qty + self.solve(n, amount, price, dp, idx + 1)
		dp[idx] = max(inc, exc)
		return dp[idx]

	def buyMaximumProducts(self, n: int, amount: int, price: List[int]) -> int:
		pair = [(price[i], i + 1) for i in range(n)]
		pair.sort()
		ans = 0
		for i in range(n):
			curAmount = pair[i][0]
			qty = pair[i][1]
			if curAmount * qty <= amount:
				ans += qty
				amount -= curAmount * qty
			else:
				ans += amount // curAmount
				amount -= curAmount * (amount // curAmount)
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = [ele for ele in enumerate(price)]
		arr.sort(key=lambda x: x[1])
		count = 0
		i = 0
		while i < n and k >= arr[i][1]:
			m = k // arr[i][1]
			if arr[i][0] + 1 >= m:
				count += m
				k -= m * arr[i][1]
			else:
				j = 0
				while k >= arr[i][1] and j < arr[i][0] + 1:
					count += 1
					k -= arr[i][1]
					j += 1
			i += 1
		return count


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, a: List[int]) -> int:
		comb = [(a[i] * (i + 1), i + 1, a[i]) for i in range(n)]
		comb.sort(key=lambda x: (x[2], -x[1]))
		c = 0
		for i in range(n):
			if k == 0:
				return c
			if comb[i][0] <= k:
				c += comb[i][1]
				k -= comb[i][0]
			elif k >= comb[i][2]:
				c += k // comb[i][2]
				k = 0
		return c


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = []
		for i in range(n):
			arr.append([price[i], i + 1])
		arr.sort()
		cnt = val = 0
		for i in range(n):
			value = arr[i][0] * arr[i][1]
			if val + value <= k:
				cnt += arr[i][1]
				val += value
			else:
				rem = k - val
				cnt += rem // arr[i][0]
				break
		return cnt


import heapq
from typing import List

class Node:

	def __init__(s, data, index):
		s.data = data
		s.index = index

	def __lt__(s, other):
		return s.data < other.data

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		l = []
		res = 0
		for i in range(n):
			node = Node(price[i], i + 1)
			heapq.heappush(l, node)
		while len(l) > 0 and l[0].data <= k:
			curr = heapq.heappop(l)
			data = curr.data
			index = curr.index
			j = index
			while j > 0:
				if j * data <= k:
					res = res + j
					k = k - j * data
					break
				j = j - 1
		return res


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		temp = []
		for i in range(n):
			temp.append([i + 1, price[i]])
		temp.sort(key=lambda x: x[1])
		ans = 0
		for i in range(n):
			res = min(temp[i][0], k // temp[i][1])
			ans += res
			k -= res * temp[i][1]
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = []
		for i in range(1, n + 1):
			ans = [price[i - 1], i]
			arr.append(ans)
		arr.sort()
		final = 0
		for i in arr:
			(node, wei) = i
			res = k // node
			if res >= wei:
				res1 = wei * node
				final += wei
				k -= res1
			elif res < wei and res >= 1:
				res1 = res * node
				final += res
				k -= res1
			else:
				break
		return final


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		stocks = []
		for i in range(n):
			stocks.append([i + 1, price[i]])
		stocks.sort(key=lambda x: x[1])
		totalPurchases = 0
		for (num, price) in stocks:
			toBuy = min(num, k // price)
			totalPurchases += toBuy
			k -= toBuy * price
		return totalPurchases


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		new = []
		for (i, j) in enumerate(price):
			new.append([i + 1, j])
		new.sort(key=lambda x: x[1], reverse=0)
		count = 0
		cost = 0
		for i in range(n):
			if cost + new[i][0] * new[i][1] <= k:
				count += new[i][0]
				cost += new[i][0] * new[i][1]
			else:
				rem = (k - cost) // new[i][1]
				count += rem
				break
		return count


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		nstocks = list(range(1, n + 1))
		data = list(zip(price, nstocks))
		data.sort(key=lambda x: x[0])
		ans = 0
		for i in range(n):
			x = min(data[i][1], k // data[i][0])
			k -= x * data[i][0]
			ans += x
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		List = []
		result = 0
		for i in range(n):
			List.append([price[i], i + 1])
		List = sorted(List, key=lambda x: x[0])
		for i in range(n):
			stock = List[i][1]
			val = List[i][0]
			if stock * val <= k:
				k -= stock * val
				result += stock
			else:
				result += k // val
				k -= val * (k // val)
		return result


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		c = 0
		arr = []
		for i in range(len(price)):
			arr.append([i + 1, price[i]])
		arr = sorted(arr, key=lambda x: x[1])
		i = 0
		while i < n and k > 0 and (arr[i][1] <= k):
			(x, y) = arr[i]
			while x != 0 and y <= k and (k != 0):
				c += 1
				x -= 1
				k -= y
			i += 1
		return c


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = [(price_, i + 1) for (i, price_) in enumerate(price)]
		arr.sort()
		i = 0
		res = 0
		while i < len(arr):
			(p, count) = arr[i]
			j = 0
			while j < count:
				if p <= k:
					res += 1
					k -= p
				j += 1
			i += 1
		return res


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = price.copy()
		arr.sort()
		res = 0
		for a in arr:
			i = price.index(a) + 1
			p = int(k / a)
			p = min(i, p)
			if p <= 0:
				continue
			k -= a * p
			res += p
			price[i - 1] = -1
		return res


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		a = [[price[i], i + 1] for i in range(n)]
		a.sort(key=lambda i: i[0])
		stock = 0
		maxstock = 0
		for (i, j) in a:
			if k < i or k < 0:
				break
			stock = min(j, k // i)
			maxstock += stock
			k -= i * stock
		return maxstock


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		price_limit = sorted([[price[i], i + 1] for i in range(n)], key=lambda x: x[0])
		max_stock = 0
		for (price, limit) in price_limit:
			if k < 0 or k < price:
				break
			stock = min(limit, k // price)
			max_stock += stock
			k -= stock * price
		return max_stock


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		stocks = [[i + 1, price[i]] for i in range(n)]
		stocks.sort(key=lambda x: x[1])
		ans = 0
		bought = 0
		for i in stocks:
			p = min(i[0], k // i[1])
			k -= i[1] * p
			ans += p
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		price_limit = [[price[i], i + 1] for i in range(n)]
		price_limit.sort(key=lambda x: x[0])
		max_stocks = 0
		for (price, limit) in price_limit:
			if k <= 0 or k < price:
				break
			stocks = min(limit, k // price)
			max_stocks += stocks
			k -= price * stocks
		return max_stocks


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		res = 0
		stock_values_limits = [(price[i], i + 1) for i in range(len(price))]
		stock_values_limits.sort(key=lambda x: x[0])
		for (price, limit) in stock_values_limits:
			if k <= 0 or price > k:
				break
			temp = min(limit, k // price)
			res += temp
			k -= price * temp
		return res


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		maxi = n * (n + 1) // 2
		arr = [[price[i], i + 1] for i in range(n)]
		arr.sort()
		cnt = 0
		for i in range(n):
			if arr[i][0] <= k:
				buy = min(arr[i][1], k // arr[i][0])
				k = k - buy * arr[i][0]
				cnt += buy
		return cnt


from typing import List

class Solution:

	def getStocksPosible(self, value, count, amt):
		if value > amt:
			return 0
		l = 1
		r = count
		while l <= r:
			mid = (l + r) // 2
			if mid * value <= amt:
				l = mid + 1
			else:
				r = mid - 1
		return r

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		price_index = [(price[i], i) for i in range(len(price))]
		price_index.sort()
		count = 0
		for i in range(len(price)):
			stocks_brought = self.getStocksPosible(price_index[i][0], price_index[i][1] + 1, k)
			if stocks_brought == 0:
				return count
			k -= price_index[i][0] * stocks_brought
			count += stocks_brought
		return count


from typing import List

def merge(A, B):
	index = []
	j = 0
	k = 0
	n = len(A) + len(B)
	for i in range(0, n):
		if A[k][0] > B[j][0]:
			index.append(B[j])
			j += 1
			if j == len(B):
				while k != len(A):
					index.append(A[k])
					k += 1
				break
		elif A[k][0] == B[j][0]:
			if A[k][1] > B[j][1]:
				index.append(B[j])
				j += 1
				if j == len(B):
					while k != len(A):
						index.append(A[k])
						k += 1
					break
			else:
				index.append(A[k])
				k += 1
				if k == len(A):
					while j != len(B):
						index.append(B[j])
						j += 1
					break
		else:
			index.append(A[k])
			k += 1
			if k == len(A):
				while j != len(B):
					index.append(B[j])
					j += 1
				break
	return index

def mergesort(arr) -> List[int]:
	A = []
	B = []
	n = len(arr)
	for i in range(0, n):
		if i < n / 2:
			A.append(arr[i])
		else:
			B.append(arr[i])
	if len(A) == 1:
		if len(B) == 1:
			return merge(A, B)
		else:
			if B[0][0] > B[1][0]:
				pass
			else:
				temp = B[1]
				B[1] = B[0]
				B[0] = temp
			return merge(A, B)
	elif len(B) == 1:
		if len(A) == 1:
			return merge(A, B)
		else:
			if A[0][0] > A[1][0]:
				temp = A[1]
				A[1] = A[0]
				A[0] = temp
			return merge(A, B)
	else:
		A = mergesort(A)
		B = mergesort(B)
	return merge(A, B)

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		stock = 0
		a = []
		for i in range(0, n):
			temp = [price[i], i]
			a.append(temp)
		index = []
		index = mergesort(a)
		for c in range(0, len(index)):
			p = int(index[c][0])
			i = int(index[c][1])
			if price[i] > k:
				break
			if (i + 1) * p > k:
				temp = k // p
				stock += temp
				k -= int(p * temp)
			else:
				stock += i + 1
				k -= (i + 1) * p
		return stock


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		l = []
		for i in range(n):
			l.append([])
			l[i].append(price[i])
			l[i].append(i + 1)
		l.sort(key=lambda x: x[0])
		r = k
		i = 0
		c = 0
		while r > 0 and i < n:
			ca = 0
			if l[i][1] > r // l[i][0]:
				ca = r // l[i][0]
			else:
				ca = l[i][1]
			r = r - ca * l[i][0]
			c = c + ca
			i += 1
		return c


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		stocks = []
		for i in range(n):
			stock = [price[i], i + 1]
			stocks.append(stock)
		stocks.sort(key=lambda stock: stock[0])
		count = 0
		for i in range(n):
			(p, c) = stocks[i]
			if k >= p * c:
				k -= p * c
				count += c
			elif k >= p:
				count += k // p
				break
		return count


import math
from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		lst = []
		for i in range(0, len(price)):
			lst.append([price[i], i + 1])
		lst.sort(key=lambda x: x[0])
		count = 0
		amount = 0
		for ele in lst:
			val = ele[0] * ele[1]
			if amount + val < k:
				count += ele[1]
				amount += val
				continue
			elif amount + val == k:
				count += ele[1]
				amount += val
				break
			else:
				left_amount = k - amount
				count += math.floor(left_amount / ele[0])
				break
		return count


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		t = []
		for i in range(n):
			t.append([price[i], -(i + 1)])
		ans = 0
		t.sort()
		for i in range(n):
			u = t[i][0]
			v = -t[i][1]
			if u * v > k:
				ans += k // u
				break
			else:
				ans += v
				k -= u * v
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		l = []
		for i in range(len(price)):
			l.append([price[i], i + 1])
		l.sort()
		c = 0
		for i in l:
			c += min(i[1], k // i[0])
			k -= i[0] * min(i[1], k // i[0])
		return c


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		a = []
		for i in range(n):
			a.append([price[i], i + 1])
		a.sort(key=lambda i: i[0])
		stock = 0
		for i in range(n):
			maxi = k // a[i][0]
			if a[i][1] < maxi:
				k -= a[i][0] * a[i][1]
				stock += a[i][1]
			else:
				k -= a[i][0] * maxi
				stock += maxi
				break
		return stock


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		stocks = [[price[i], i + 1] for i in range(n)]
		stocks.sort()
		res = 0
		for i in range(n):
			pGoes = k // stocks[i][0]
			if stocks[i][1] <= pGoes:
				res += stocks[i][1]
				k = k - stocks[i][1] * stocks[i][0]
			else:
				res += pGoes
				k = k - pGoes * stocks[i][0]
		return res


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, arr: List[int]) -> int:
		list = []
		for i in range(n):
			list.append([i + 1, arr[i]])
		list.sort(key=lambda x: x[1])
		ans = 0
		for i in range(n):
			x = list[i][0]
			while x > 0 and k - list[i][1] >= 0:
				ans += 1
				k = k - list[i][1]
				x -= 1
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		a = [[i + 1, price[i]] for i in range(n)]
		b = sorted(a, key=lambda x: (x[1], -x[0]))
		count = 0
		for i in range(n):
			x = b[i][0] * b[i][1]
			if x <= k:
				count += b[i][0]
				k -= x
			else:
				j = 1
				while b[i][1] * j <= k:
					j += 1
				j -= 1
				count += j
				return count
		return count


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		stocks = []
		count = 0
		for i in range(n):
			stocks.append([i + 1, price[i]])
		stocks.sort(key=lambda x: x[1])
		for i in range(n):
			day = stocks[i][0]
			price = stocks[i][1]
			if price * day <= k:
				count += day
				k -= price * day
			else:
				count += k // price
				break
		return count


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = [(v, i) for (i, v) in enumerate(price, start=1)]
		arr.sort(key=lambda x: (x[0], x[1]))
		ans = 0
		for (cost, stocks) in arr:
			x = min(stocks, k // cost)
			ans += x
			k -= cost * x
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		l = []
		for i in range(n):
			l.append([price[i], i + 1])
		l.sort(key=lambda i: i[0])
		s = 0
		i = c = 0
		while s <= k and i < n:
			s = s + l[i][0] * l[i][1]
			c = c + l[i][1]
			i += 1
		i = i - 1
		while s > k:
			s = s - l[i][0]
			c = c - 1
		return c


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = [[price[i], i + 1] for i in range(n)]
		arr.sort()
		purchase = 0
		i = 0
		stocks = 0
		while i < n:
			for j in range(arr[i][1]):
				if purchase < k:
					purchase += arr[i][0]
					stocks += 1
				if purchase > k:
					stocks -= 1
					purchase -= arr[i][0]
					break
			i += 1
		return stocks


class Solution:

	def buyMaximumProducts(self, n, k, price):
		List = []
		for i in range(0, len(price)):
			List.append((price[i], i + 1))
		List = sorted(List, key=lambda x: x[0])
		count = 0
		for i in range(0, len(List)):
			stocks = List[i][1]
			prices = List[i][0]
			if stocks * prices <= k:
				k = k - stocks * prices
				count += stocks
			else:
				count += k // prices
				k -= prices * (k // prices)
		return count


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		arr = [[ele, i + 1] for (i, ele) in enumerate(price)]
		arr.sort()
		ans = 0
		for temp in arr:
			if temp[0] * temp[1] <= k:
				k -= temp[0] * temp[1]
				ans += temp[1]
			else:
				ans += k // temp[0]
				k = k % temp[0]
			if k == 0:
				break
		return ans


from typing import List

class Solution:

	def buyMaximumProducts(self, n: int, k: int, price: List[int]) -> int:
		l = [[price[i], i + 1] for i in range(n)]
		l.sort(key=lambda x: x[0])
		count = 0
		for i in range(len(l)):
			if k > l[i][0] * l[i][1]:
				k = k - l[i][0] * l[i][1]
				count += l[i][1]
			else:
				while k < l[i][0] * l[i][1]:
					l[i][1] -= 1
				k = k - l[i][0] * l[i][1]
				count += l[i][1]
		return count