There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.
The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers. 
 
Example 1:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

 
Constraints:

1 <= n <= 10^5
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8
1 <= k <= n

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms

Starter code: class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        

Solutions:
class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		mod = 10 ** 9 + 7
		order = sorted(range(n), key=lambda i: efficiency[i], reverse=True)
		heap = []
		filled = 0
		rec = 0
		speed_sum = 0
		for i in order:
			if filled < k:
				heapq.heappush(heap, speed[i])
				filled += 1
				speed_sum += speed[i]
			else:
				removed = heapq.heappushpop(heap, speed[i])
				speed_sum += speed[i] - removed
			rec = max(rec, speed_sum * efficiency[i])
		return rec % mod


from heapq import *

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		ids = [i for i in range(n)]
		ids = sorted(ids, key=lambda x: -efficiency[x])
		(max_perf, heap) = (0, [])
		sum = 0
		for i in ids:
			if len(heap) == k:
				sum -= heappop(heap)
			heappush(heap, speed[i])
			sum += speed[i]
			max_perf = max(max_perf, sum * efficiency[i])
		return max_perf % (10 ** 9 + 7)


from heapq import *

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		engineers = sorted(zip(speed, efficiency), key=lambda x: -x[1])
		min_heap = []
		max_performance = 0
		curr_speed_sum = 0
		for i in range(len(engineers)):
			speed = engineers[i][0]
			efficiency = engineers[i][1]
			if len(min_heap) < k:
				curr_speed_sum += speed
				heappush(min_heap, speed)
			elif speed > min_heap[0]:
				top_kth_speed = heappushpop(min_heap, speed)
				curr_speed_sum -= top_kth_speed
				curr_speed_sum += speed
			else:
				continue
			max_performance = max(max_performance, curr_speed_sum * efficiency)
		return max_performance % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n, speed, efficiency, k):
		teams = sorted(zip(efficiency, speed), reverse=True)
		pq = []
		max_perf = s = 0
		for i in range(n):
			heapq.heappush(pq, teams[i][1])
			s += teams[i][1]
			if i >= k:
				s -= heapq.heappop(pq)
			max_perf = max(max_perf, s * teams[i][0])
		return max_perf % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		term = 10 ** 9 + 7
		heap = []
		lst = [i for i in range(n)]
		lst.sort(key=lambda x: (-efficiency[x], -speed[x]))
		ret = 0
		acc = 0
		for i in range(k):
			idx = lst[i]
			acc += speed[idx]
			heap.append(speed[idx])
			ret = max(ret, acc * efficiency[idx])
		import heapq
		heapq.heapify(heap)
		for i in range(k, n):
			idx = lst[i]
			if heap[0] < speed[idx]:
				acc = acc - heap[0] + speed[idx]
				heapq.heapreplace(heap, speed[idx])
				ret = max(ret, acc * efficiency[idx])
		return ret % term


import heapq

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		bestTeamHeap = []
		heapSum = 0
		bestTeamScore = 0
		for (e, s) in sorted(zip(efficiency, speed), reverse=True):
			heapq.heappush(bestTeamHeap, s)
			heapSum += s
			if len(bestTeamHeap) > k:
				heapSum -= heapq.heappop(bestTeamHeap)
			bestTeamScore = max(bestTeamScore, e * heapSum)
		return bestTeamScore % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		ls = list(zip(speed, efficiency))
		ls.sort(key=lambda x: -x[1])
		(hq, ssum) = ([], 0)
		ans = 0
		for (i, (s, e)) in enumerate(ls):
			if i >= k:
				(s0, e0) = heapq.heappop(hq)
				ssum -= s0
			heapq.heappush(hq, (s, e))
			ssum += s
			ans = max(ans, ssum * e)
		return ans % 1000000007


class Solution:

	def maxPerformance(self, n, speed, efficiency, k):
		ls = list(zip(speed, efficiency))
		ls.sort(key=lambda x: -x[1])
		HEAP = []
		tsum = 0
		ans = 0
		for i in range(n):
			if i >= k:
				(speed, efficiency) = heapq.heappop(HEAP)
				tsum -= speed
			heapq.heappush(HEAP, ls[i])
			tsum += ls[i][0]
			ans = max(ans, tsum * ls[i][1])
		return ans % 1000000007


from heapq import heappush, heappop

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		comb = sorted(zip(efficiency, speed), reverse=True)
		min_heap = []
		perf = 0
		s = 0
		for i in range(n):
			heappush(min_heap, comb[i][1])
			s += comb[i][1]
			if i >= k:
				s -= heappop(min_heap)
			perf = max(perf, s * comb[i][0])
		return perf % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		h = []
		res = sSum = 0
		for (e, s) in sorted(zip(efficiency, speed), reverse=1):
			heapq.heappush(h, s)
			sSum += s
			if len(h) > k:
				sSum -= heapq.heappop(h)
			res = max(res, sSum * e)
		return res % (10 ** 9 + 7)


from heapq import *

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		totalSpeed = 0
		res = 0
		heap = []
		for (e, s) in sorted(zip(efficiency, speed), reverse=True):
			totalSpeed += s
			heappush(heap, s)
			if len(heap) > k:
				totalSpeed -= heappop(heap)
			res = max(res, totalSpeed * e)
		return res % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		items = sorted(zip(speed, efficiency), key=lambda item: (-item[1], -item[0]))
		heap = []
		s = 0
		res = 0
		for item in items:
			if len(heap) < k or item[0] > heap[0][0]:
				if len(heap) == k:
					popped = heapq.heappop(heap)
					s -= popped[0]
				heapq.heappush(heap, item)
				s += item[0]
				res = max(res, s * item[1])
		return res % (10 ** 9 + 7)


from heapq import heappop, heappush

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		es_list = [[-e, s] for (s, e) in zip(speed, efficiency)]
		es_list.sort()
		queue = []
		total_speed = 0
		cur_eff = 0
		res = 0
		for (e, s) in es_list:
			if -e < cur_eff:
				res = max(res, cur_eff * total_speed)
			if len(queue) == k:
				if not queue or queue[0] < s:
					pre_s = heappop(queue)
					total_speed -= pre_s
			if not queue or len(queue) < k:
				heappush(queue, s)
				total_speed += s
				cur_eff = -e
		return max(res, total_speed * cur_eff) % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		mod = 10 ** 9 + 7
		eff_speed = sorted(zip(efficiency, speed), reverse=True)
		n = len(eff_speed)
		i = 0
		speed_h = []
		speed_sum = 0
		max_perf = 0
		start = 0
		while i < n:
			while i == start or (i < n and eff_speed[i][0] == eff_speed[i - 1][0]):
				heapq.heappush(speed_h, eff_speed[i][1])
				speed_sum += eff_speed[i][1]
				if len(speed_h) > k:
					speed_sum -= heapq.heappop(speed_h)
				i += 1
			start = i
			cur_efficiency = eff_speed[i - 1][0]
			max_perf = max(max_perf, cur_efficiency * speed_sum)
		return max_perf % mod


class Solution:

	def maxPerformance1(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		people = sorted(zip(speed, efficiency), key=lambda x: -x[1])
		(total, sumSpeed) = (0, 0)
		for (s, e) in people:
			sumSpeed += s
			total = max(total, sumSpeed * e)
		return total

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		people = sorted(zip(speed, efficiency), key=lambda x: -x[1])
		print(people)
		(result, sum_speed) = (0, 0)
		min_heap = []
		for (i, (s, e)) in enumerate(people):
			if i < k:
				sum_speed += s
				heapq.heappush(min_heap, s)
			elif s > min_heap[0]:
				sum_speed += s - heapq.heappushpop(min_heap, s)
			result = max(result, sum_speed * e)
		return result % 1000000007


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		es = list(zip(efficiency, speed))
		es.sort(reverse=True)
		speed_sum = 0
		max_prod = 0
		heap = []
		for i in range(k):
			(eff, speed) = es[i]
			speed_sum += speed
			max_prod = max(max_prod, speed_sum * eff)
			heap.append(speed)
		heapq.heapify(heap)
		for i in range(k, n):
			(cur_eff, cur_speed) = es[i]
			heapq.heappush(heap, cur_speed)
			speed_sum -= heapq.heappop(heap)
			speed_sum += cur_speed
			max_prod = max(max_prod, speed_sum * cur_eff)
		return max_prod % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n, speed, efficiency, k):
		worker = []
		for i in range(n):
			worker.append([speed[i], efficiency[i]])
		worker.sort(key=lambda x: -x[1])
		print(worker)
		import heapq
		total = 0
		heap = []
		res = 0
		for i in range(k):
			total += worker[i][0]
			minE = worker[i][1]
			heapq.heappush(heap, worker[i][0])
			res = max(res, total * minE)
		for i in range(k, n):
			if worker[i][0] > heap[0]:
				total += -heap[0] + worker[i][0]
				minE = worker[i][1]
				res = max(res, minE * total)
				heapq.heappop(heap)
				heapq.heappush(heap, worker[i][0])
		return res % 1000000007


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		if n == 0:
			return 0
		engineers = [[speed[i], efficiency[i]] for i in range(n)]
		engineers.sort(key=lambda x: x[1], reverse=True)
		mod = 1000000007
		pq = []
		sum_speed = 0
		min_efficiency = engineers[0][1]
		max_performance = 0
		for e in engineers:
			heapq.heappush(pq, e)
			sum_speed += e[0]
			if len(pq) > k:
				tmp = heapq.heappop(pq)
				sum_speed -= tmp[0]
				if tmp != e:
					min_efficiency = e[1]
			else:
				min_efficiency = e[1]
			max_performance = max(max_performance, sum_speed * min_efficiency)
		return max_performance % mod


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		res = sorted([(speed[i], efficiency[i]) for i in range(n)], key=lambda x: [-x[1], -x[0]])
		num = 0
		sums = []
		ss = 0
		maxi = 0
		for (s, e) in res:
			if num < k:
				heappush(sums, s)
				ss += s
				num += 1
				maxi = max(maxi, ss * e)
			else:
				rmv = heappushpop(sums, s)
				ss = ss - rmv + s
				maxi = max(maxi, ss * e)
		return maxi % (10 ** 9 + 7)


import heapq

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		mod = 10 ** 9 + 7
		comb = [(speed[i], efficiency[i]) for i in range(n)]
		comb.sort(key=lambda x: -x[1])
		total_speed = 0
		ans = 0
		pq = []
		for i in range(n):
			heapq.heappush(pq, comb[i][0])
			total_speed += comb[i][0]
			if len(pq) > k:
				total_speed -= heapq.heappop(pq)
			low_eff = comb[i][1]
			ans = max(ans, total_speed * low_eff)
		return ans % mod


import heapq

class Solution:

	def maxPerformance(self, n, speed, efficiency, k):
		engs = []
		heapq.heapify(engs)
		for i in range(n):
			heapq.heappush(engs, (-efficiency[i], speed[i]))
		speedtotal = 0
		totalperf = 0
		current_team = []
		heapq.heapify(current_team)
		for i in range(k):
			temp = heapq.heappop(engs)
			speedtotal += temp[1]
			totalperf = max(totalperf, speedtotal * -temp[0])
			heapq.heappush(current_team, temp[1])
		for j in range(k, n):
			temp = heapq.heappop(engs)
			if temp[1] > current_team[0]:
				speedtotal -= current_team[0]
				speedtotal += temp[1]
				totalperf = max(totalperf, -temp[0] * speedtotal)
				heapq.heappop(current_team)
				heapq.heappush(current_team, temp[1])
		return totalperf % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		l = [(x, y) for (x, y) in zip(speed, efficiency)]
		l = sorted(l, key=lambda x: (x[1], -x[0]))
		ma = 0
		q = []
		s = 0
		for i in range(len(l) - 1, -1, -1):
			mi = l[i][1]
			heapq.heappush(q, l[i][0])
			s += l[i][0]
			if len(q) > k:
				s -= heapq.heappop(q)
			ma = max(ma, s * l[i][1])
		return ma % (10 ** 9 + 7)


import heapq

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		engineers = [(speed[i], efficiency[i]) for i in range(n)]
		engineers.sort(key=lambda x: (-x[1], x[0]))
		result = 0
		heap = []
		totalSum = 0
		for i in range(n):
			while len(heap) >= k:
				totalSum -= heapq.heappop(heap)
			result = max(result, (totalSum + engineers[i][0]) * engineers[i][1])
			heapq.heappush(heap, engineers[i][0])
			totalSum += engineers[i][0]
		return result % (10 ** 9 + 7)


class Solution(object):

	def maxPerformance(self, n, speed, efficiency, k):
		worker = []
		for i in range(n):
			worker.append([speed[i], efficiency[i]])
		worker = sorted(worker, key=lambda x: x[1], reverse=True)
		print(worker)
		import heapq
		total = 0
		heap = []
		res = 0
		for i in range(k):
			total += worker[i][0]
			minE = worker[i][1]
			heapq.heappush(heap, worker[i][0])
			res = max(res, total * minE)
		for i in range(k, n):
			if worker[i][0] > heap[0]:
				total += -heap[0] + worker[i][0]
				minE = worker[i][1]
				res = max(res, minE * total)
				heapq.heappop(heap)
				heapq.heappush(heap, worker[i][0])
		return res % 1000000007

	def cmp(self, w1, w2):
		if w1[1] > w2[1]:
			return -1
		elif w1[1] == w2[1]:
			return 0
		else:
			return 1


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		people = sorted(zip(speed, efficiency), key=lambda x: x[1], reverse=True)
		(result, sum_speed) = (0, 0)
		min_heap = []
		print(people)
		for (i, (s, e)) in enumerate(people):
			if i < k:
				sum_speed += s
				heapq.heappush(min_heap, s)
			elif s > min_heap[0]:
				sum_speed += s - heapq.heappushpop(min_heap, s)
			result = max(result, sum_speed * e)
			print(result)
		return result % (pow(10, 9) + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		(pq, largelst) = ([], [])
		for i in range(n):
			heapq.heappush(pq, (-efficiency[i], speed[i]))
		(mx, sm) = (0, 0)
		while pq:
			pop = heapq.heappop(pq)
			eff = -pop[0]
			heapq.heappush(largelst, pop[1])
			sm += pop[1]
			while len(largelst) > k:
				rm = heapq.heappop(largelst)
				sm -= rm
			mx = max(mx, sm * eff)
		return mx % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		engineers = sorted(zip(speed, efficiency), key=lambda eng: eng[1], reverse=True)
		h = []
		res = 0
		speedSum = 0
		for (s, e) in engineers:
			heapq.heappush(h, s)
			speedSum += s
			if len(h) > k:
				speedSum -= h[0]
				heapq.heappop(h)
			res = max(res, speedSum * e)
		return res % (10 ** 9 + 7)


from heapq import heappush, heappop

class Engineer:

	def __init__(self, speed, efficiency):
		self.speed = speed
		self.efficiency = efficiency

	def __str__(self):
		return str(self.speed) + ',' + str(self.efficiency)

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		engineers = [Engineer(speed[i], efficiency[i]) for i in range(n)]
		engineers.sort(key=lambda x: x.efficiency, reverse=True)
		performance = 0
		maxSpeeds = []
		sumOfSpeeds = 0
		for (index, engineer) in enumerate(engineers):
			heappush(maxSpeeds, [engineer.speed, index, engineer])
			sumOfSpeeds += engineer.speed
			if len(maxSpeeds) > k:
				sumOfSpeeds -= heappop(maxSpeeds)[2].speed
			performance = max(performance, engineer.efficiency * sumOfSpeeds)
		return performance % (10 ** 9 + 7)


import heapq

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		lst = sorted(zip(efficiency, speed), reverse=True)
		p = []
		sum_speed = 0
		res = 0
		for (e, s) in lst:
			sum_speed += s
			heapq.heappush(p, s)
			if len(p) > k:
				sum_speed -= heapq.heappop(p)
			val = e * sum_speed
			res = max(res, val)
		return res % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		temp = []
		for i in range(len(efficiency)):
			temp.append([efficiency[i], speed[i]])
		temp.sort(reverse=True)
		heap = []
		cur_sum = 0
		result = 0
		for i in range(len(temp)):
			heapq.heappush(heap, (temp[i][1], i))
			cur_sum += temp[i][1]
			if len(heap) > k:
				cur_sum -= heapq.heappop(heap)[0]
			result = max(result, cur_sum * temp[i][0])
		return result % (10 ** 9 + 7)


from heapq import heappush, heappop

class Engineer:

	def __init__(self, speed, efficiency):
		self.speed = speed
		self.efficiency = efficiency

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		engineers = []
		for i in range(n):
			engineers.append(Engineer(speed[i], efficiency[i]))
		engineers.sort(key=lambda eng: eng.efficiency, reverse=True)
		minHeap = []
		(maxPerform, sumOfSpeed) = (0, 0)
		for (i, eng) in enumerate(engineers):
			sumOfSpeed += eng.speed
			heappush(minHeap, [eng.speed, i, eng])
			if len(minHeap) > k:
				sumOfSpeed -= heappop(minHeap)[2].speed
			maxPerform = max(sumOfSpeed * eng.efficiency, maxPerform)
		return maxPerform % (10 ** 9 + 7)


from heapq import heappush, heappop

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		data = sorted(list(zip(efficiency, speed)), reverse=True)
		pq = []
		(current_eff, total) = (float('inf'), 0)
		answer = 0
		print(data)
		for (eff, spd) in data:
			current_eff = eff
			total += spd
			heappush(pq, spd)
			if len(pq) > k:
				total -= heappop(pq)
			answer = max(answer, current_eff * total)
		return answer % int(1000000000.0 + 7)


from heapq import heappush, heappop

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		M = 10 ** 9 + 7
		eff_pq = []
		sp_pq = []
		speed_sum = 0
		for (idx, eff) in enumerate(efficiency):
			heappush(eff_pq, (-eff, idx))
		res = 0
		while len(eff_pq) > 0:
			(neg_eff, idx) = heappop(eff_pq)
			eff = -neg_eff
			heappush(sp_pq, speed[idx])
			speed_sum += speed[idx]
			if len(sp_pq) > k:
				sp_pop = heappop(sp_pq)
				speed_sum -= sp_pop
			res = max(res, eff * speed_sum)
		return res % M


import heapq

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		a = list(zip(efficiency, speed))
		a.sort(reverse=True)
		pq = []
		mp = s = 0
		for i in range(n):
			heapq.heappush(pq, a[i][1])
			s += a[i][1]
			if i >= k:
				s -= heapq.heappop(pq)
			mp = max(mp, s * a[i][0])
		return mp % (10 ** 9 + 7)


from heapq import heappush, heappop

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		mod = 10 ** 9 + 7
		people = [[speed[i], efficiency[i]] for i in range(n)]
		people.sort(key=lambda x: -x[1])
		res = 0
		h = []
		total_speed = 0
		for (i, (s, e)) in enumerate(people):
			heappush(h, s)
			total_speed += s
			if len(h) > k:
				total_speed -= heappop(h)
			res = max(res, total_speed * e)
		return res % mod


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		MOD = 10 ** 9 + 7
		comb = [(speed[i], efficiency[i]) for i in range(n)]
		comb.sort(key=lambda x: -x[1])
		total_speed = 0
		ans = 0
		pq = []
		for i in range(n):
			heapq.heappush(pq, comb[i][0])
			total_speed += comb[i][0]
			if len(pq) > k:
				total_speed -= heapq.heappop(pq)
			low_eff = comb[i][1]
			ans = max(ans, total_speed * low_eff)
		return ans % MOD
		MOD = 10 ** 9 + 7
		combo = []
		for i in range(n):
			heapq.heappush(combo, (-efficiency[i], speed[i]))
		tmp = []
		(ans, currsum) = (0, 0)
		while combo:
			(curre, currs) = heapq.heappop(combo)
			tmp.append(currs)
			currsum += currs
			if len(tmp) > k:
				currsum -= heapq.heappop(tmp)
			ans = max(ans, -currsum * curre % MOD)
		return ans


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		worker = []
		for i in range(n):
			worker.append([speed[i], efficiency[i]])
		worker.sort(key=lambda x: x[1], reverse=True)
		import heapq
		total = 0
		heap = []
		res = 0
		for i in range(k):
			total += worker[i][0]
			minE = worker[i][1]
			heapq.heappush(heap, worker[i][0])
			res = max(res, total * minE)
		for i in range(k, n):
			if worker[i][0] > heap[0]:
				total += -heap[0] + worker[i][0]
				minE = worker[i][1]
				res = max(res, minE * total)
				heapq.heappushpop(heap, worker[i][0])
		return res % 1000000007


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		sorting = sorted([(s, i) for (i, s) in enumerate(speed)])
		speedset = set((i for (_, i) in sorting[len(sorting) - k:]))
		ssum = sum((s for (s, _) in sorting[len(sorting) - k:]))
		removed = set()
		idx = len(sorting) - k
		ans = 0
		for (e, i) in sorted([(e, i) for (i, e) in enumerate(efficiency)]):
			if i in speedset:
				ans = max(ans, e * ssum)
				speedset.remove(i)
				ssum -= speed[i]
				idx -= 1
				while idx >= 0 and sorting[idx][1] in removed:
					idx -= 1
				if idx >= 0:
					speedset.add(sorting[idx][1])
					ssum += sorting[idx][0]
			else:
				ans = max(ans, e * (ssum - sorting[idx][0] + speed[i]))
			removed.add(i)
		return ans % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		a = [(s, e) for (s, e) in zip(speed, efficiency)]
		if k == 1:
			return max([s * e for (s, e) in a])
		a.sort(key=lambda x: -x[1])
		ret = 0
		q = []
		s_sum = 0
		for (s, e) in a:
			ret = max(ret, (s_sum + s) * e)
			if len(q) >= k - 1:
				if q[0] < s:
					x = heapq.heappop(q)
					s_sum = s_sum + s - x
					heapq.heappush(q, s)
			else:
				heapq.heappush(q, s)
				s_sum += s
		return ret % (10 ** 9 + 7)


import heapq

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		pairs = list(zip(efficiency, speed))
		pairs.sort(key=lambda x: (-x[0], -x[1]))
		arr = []
		res = 0
		sum_spd = 0
		for (eff, spd) in pairs:
			if len(arr) < k:
				sum_spd += spd
				heapq.heappush(arr, spd)
			elif spd > arr[0]:
				sum_spd += spd - heapq.heappushpop(arr, spd)
			res = max(res, sum_spd * eff)
		return res % (10 ** 9 + 7)


from sortedcontainers import SortedList

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		(workers, MOD) = (SortedList(), 10 ** 9 + 7)
		ret = ss = 0
		for (e, s) in sorted(zip(efficiency, speed), reverse=True):
			workers.add(s)
			ss += s
			if len(workers) > k:
				ss -= workers.pop(0)
			ret = max(ret, e * ss)
		return ret % MOD


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		q = []
		worker = []
		for (s, e) in zip(speed, efficiency):
			worker.append([s, e])
		(ans, speeds, minEff) = (0, 0, float('inf'))
		for (s, e) in sorted(worker, key=lambda x: -x[1]):
			if len(q) < k:
				heapq.heappush(q, [s, e])
				speeds += s
				minEff = min(minEff, e)
			elif s > q[0][0]:
				(ts, te) = heapq.heappop(q)
				speeds = speeds - ts + s
				minEff = e
				heapq.heappush(q, [s, e])
			ans = max(ans, speeds * minEff)
		return ans % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		heap = []
		total = 0
		pairs = list(zip(speed, efficiency))
		pairs.sort(key=lambda x: -x[1])
		res = 0
		MOD = 10 ** 9 + 7
		for (i, (s, e)) in enumerate(pairs):
			res = max(e * (total + s), res)
			if len(heap) < k - 1:
				heapq.heappush(heap, s)
				total += s
			elif heap and s > heap[0]:
				total -= heapq.heappop(heap)
				heapq.heappush(heap, s)
				total += s
		return res % MOD


from queue import PriorityQueue

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		mod = 10 ** 9 + 7
		if k == 1:
			return max([speed[i] * efficiency[i] for i in range(n)]) % mod
		engs = sorted([(efficiency[i], speed[i]) for i in range(n)])
		others = PriorityQueue()
		maxi = 0
		otherSum = 0
		for i in range(n - 1, -1, -1):
			maxi = max(maxi, (engs[i][1] + otherSum) * engs[i][0])
			otherSum += engs[i][1]
			others.put(engs[i][1])
			while others.qsize() > k - 1:
				otherSum -= others.get()
		return maxi % mod


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		unit = sorted([(s, e) for (s, e) in zip(speed, efficiency)], key=lambda x: x[1], reverse=True)
		max_res = -1
		curr_sum = 0
		MOD = 10 ** 9 + 7
		heap = []
		for (s, e) in unit:
			curr_sum += s
			max_res = max(max_res, curr_sum * e)
			heapq.heappush(heap, s)
			if len(heap) >= k:
				curr_sum -= heapq.heappop(heap)
		return max_res % MOD


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		arr = list(zip(efficiency, speed))
		arr.sort(reverse=True)
		counter = 0
		curr_max = 0
		heap = []
		for i in arr:
			curr_max = max(curr_max, i[0] * (counter + i[1]))
			heapq.heappush(heap, i[1])
			counter += i[1]
			if len(heap) > k - 1:
				counter -= heapq.heappop(heap)
		return curr_max % (10 ** 9 + 7)


import heapq

class Solution:

	def maxPerformance(self, n: int, S: List[int], E: List[int], k: int) -> int:
		tmp = []
		for (x, y) in zip(S, E):
			tmp.append([y, x])
		tmp.sort(reverse=True)
		stack = []
		sums = 0
		res = 0
		for i in range(n):
			nk = tmp[i][0]
			sums += tmp[i][1] - (heapq.heappop(stack) if len(stack) == k else 0)
			heapq.heappush(stack, tmp[i][1])
			res = max(res, nk * sums)
		return res % 1000000007


import heapq

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		arr = zip(efficiency, speed)
		arr = sorted(arr, key=lambda x: (-x[0], -x[1]))
		pq = []
		(maxSoFar, currSum) = (0, 0)
		for (eff, sp) in arr:
			currSum += sp
			heapq.heappush(pq, sp)
			if len(pq) == k + 1:
				currSum -= heapq.heappop(pq)
			maxSoFar = max(maxSoFar, currSum * eff)
		return maxSoFar % 1000000007


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		M = 10 ** 9 + 7
		heap = []
		ans = t = 0
		for (e, s) in sorted(zip(efficiency, speed), reverse=True):
			t += s
			heapq.heappush(heap, s)
			if len(heap) == k + 1:
				t -= heapq.heappop(heap)
			ans = max(ans, t * e)
		return ans % M


from heapq import heappush, heappop

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		speed_heap = []
		speed_sum = 0
		max_performance = 0
		for (cur_efficiency, cur_speed) in sorted(zip(efficiency, speed), reverse=True):
			heappush(speed_heap, cur_speed)
			speed_sum += cur_speed
			if len(speed_heap) > k:
				speed_sum -= heappop(speed_heap)
			max_performance = max(max_performance, speed_sum * cur_efficiency)
		return max_performance % (10 ** 9 + 7)


import heapq

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		if k < 1:
			return 0
		best = 0
		heap = []
		cur_sum = 0
		data = sorted(list(zip(speed, efficiency)), key=lambda x: -x[1])
		for (s, e) in data:
			if len(heap) < k:
				cur_sum += s
				heapq.heappush(heap, s)
				if cur_sum * e > best:
					best = cur_sum * e
			else:
				if (cur_sum - heap[0] + s) * e > best:
					best = (cur_sum - heap[0] + s) * e
				if s > heap[0]:
					cur_sum += s - heap[0]
					heapq.heappush(heap, s)
					heapq.heappop(heap)
		return best % 1000000007


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		q = []
		sum_speed = 0
		res = 0
		for (e, s) in sorted(zip(efficiency, speed), reverse=True):
			sum_speed += s
			heapq.heappush(q, s)
			while len(q) > k:
				sum_speed -= heapq.heappop(q)
			res = max(res, e * sum_speed)
		return res % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		MOD = 10 ** 9 + 7
		pq = []
		engineers = list(zip(speed, efficiency))
		engineers.sort(key=lambda tup: -tup[1])
		performance = 0
		tot_speed = 0
		for engineer in engineers:
			min_efficiency = engineer[1]
			if len(pq) == k:
				if pq[0] < engineer[0]:
					bad_speed = heapq.heappop(pq)
					heapq.heappush(pq, engineer[0])
					tot_speed = tot_speed - bad_speed + engineer[0]
			else:
				heapq.heappush(pq, engineer[0])
				tot_speed += engineer[0]
			performance = max(performance, tot_speed * min_efficiency)
		return performance % MOD


from heapq import heappop, heappush

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		hh = [[efficiency[ii], speed[ii]] for ii in range(n)]
		hh.sort(reverse=True)
		heap = []
		cursum = 0
		cureff = hh[0][0]
		ans = 0
		for (ih, [e, s]) in enumerate(hh):
			heappush(heap, (s, ih))
			(tops, topind) = heap[0]
			cursum = cursum + s
			if len(heap) > k:
				heappop(heap)
				cursum = cursum - hh[topind][1]
			cureff = e
			ans = max(ans, cureff * cursum)
		return ans % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		MOD = 10 ** 9 + 7
		es = sorted(zip(efficiency, speed))
		result = 0
		heap = [0]
		s = 0
		for i in range(n - 1, -1, -1):
			if len(heap) < k:
				heapq.heappush(heap, es[i][1])
				s = s + es[i][1]
			elif es[i][1] > heap[0]:
				s = s + es[i][1] - heapq.heappushpop(heap, es[i][1])
			p = es[i][0] * s
			result = max(result, p)
		return result % MOD


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		MOD = 10 ** 9 + 7
		combo = []
		for i in range(n):
			heapq.heappush(combo, (-efficiency[i], -speed[i]))
		tmp = []
		(ans, currsum) = (0, 0)
		while combo:
			(curre, currs) = heapq.heappop(combo)
			heapq.heappush(tmp, -currs)
			currsum -= currs
			if len(tmp) > k:
				currsum -= heapq.heappop(tmp)
			ans = max(ans, -currsum * curre)
		return ans % MOD


import heapq

class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		pairs = [(-efficiency[i], speed[i]) for i in range(n)]
		heapq.heapify(pairs)
		t = 0
		res = 0
		usedSpeeds = []
		cur = 0
		while pairs:
			(e, s) = heapq.heappop(pairs)
			cur += s
			t += 1
			if t <= k:
				res = max(res, -1 * e * cur)
			elif t > k:
				cur -= heapq.heappop(usedSpeeds)
				res = max(res, -1 * e * cur)
			heapq.heappush(usedSpeeds, s)
		return res % (10 ** 9 + 7)


class Solution:

	def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
		vals = [(speed[i], efficiency[i]) for i in range(n)]
		vals.sort(reverse=True, key=lambda x: x[1])
		speed = 0
		ans = 0
		pq = []
		for i in range(n):
			heapq.heappush(pq, vals[i][0])
			speed += vals[i][0]
			if len(pq) > k:
				speed -= heapq.heappop(pq)
			ans = max(ans, speed * vals[i][1])
		return ans % (10 ** 9 + 7)