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

Difficulty: interview

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:

        # sort by descending efficiency order
        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)
            else:
                # already have top k-speed in heap, swap it out if found a faster speed
                if 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])
        # build heap
        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%1_000_000_007
   
            
            
                
            
            


class Solution:
    def maxPerformance(self, n, speed, efficiency, k):
       # n = speed.len()
        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%1_000_000_007

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)


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:
            #print(e, s, queue, total_speed, res)
            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)
        
        # try out all possible least efficient member
        # keep track of highest k speed before and including this member
        
        
        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
            # prev_min = heapq.heappop(heap)
            # speed_sum -= prev_min
            # speed_sum += cur_speed
            max_prod = max(max_prod, speed_sum * cur_eff)
            # heapq.heappush(heap, max(prev_min, cur_speed))
            # speed_sum -= cur_speed
            # speed_sum += max(prev_min, cur_speed)
            
        
        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
        
    # 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:
        # Sort engineer by efficiency
        # for all engineer higher than efficiency x,
        # keep the ones with high speed
        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 : # The newly added engineer might be eliminated
                    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

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:        
        sums = []
        ss = 0
        maxi = 0
        for s,e in sorted([(speed[i], efficiency[i]) for i in range(n)], key = lambda x: [-x[1], -x[0]]):
            heappush(sums, s)
            ss += s
            if len(sums) > k:
                rmv = heappop(sums)
                ss -= rmv
            maxi = max(maxi, ss*e)

        return maxi%(10**9+7)


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]))
        #efficiency=sorted(efficiency)
        
        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:
        h=[]  #最小堆，存放挑选的工程师的速度
        ssum=0
        res=0
        for e,s in sorted(zip(efficiency,speed),reverse=True):
            heapq.heappush(h,s)
            ssum+=s
            if len(h)>k:
                ssum-=heapq.heappop(h)
            res=max(res,ssum*e)
        return res%(10**9+7)


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)


import heapq

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        res = 0
        hired, curr_sum = [], 0
        for e, s in sorted(zip(efficiency, speed), reverse=True):
            heapq.heappush(hired, s)
            curr_sum += s
            if len(hired) > k:
                curr_sum -= heapq.heappop(hired)
            res = max(res, curr_sum * e)
        return res % (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(1e9 + 7)

from heapq import heappush, heappop
class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        ## based on the hints
        ## since The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers
        ## we process engineer one by one in desceding order of his efficiency
        ## and keep track the running sum of the previous k largest speeds
        
        ## two priority queues
        M = 10**9+7
        eff_pq = [] ## max heap
        sp_pq = [] ## min heap
        speed_sum = 0 ## track the sum of largest k speeds
        ## push all efficiency and indexes into a max-heap
        for idx, eff in enumerate(efficiency):
            heappush(eff_pq, (-eff, idx))
        
        res = 0
        while len(eff_pq)>0:
            neg_eff, idx = heappop(eff_pq) ## process engineer one by one in desceding order of his efficiency
            eff = -neg_eff
            heappush(sp_pq, speed[idx]) ## push his speed into min-heap
            speed_sum += speed[idx] ## keep tracking the running sum
            
            ## maintain the priority queue with size <= k
            if len(sp_pq) > k:
                sp_pop = heappop(sp_pq)
                speed_sum -= sp_pop ## keep tracking the running sum
                
            ## note that a team be at most k engineers, which mean it can be less than k
            res = max(res, eff*speed_sum) 
            
        return res % M
# 6
# [2,10,3,1,5,8]
# [5,4,3,9,7,2]
# 2
# 3
# [2,8,2]
# [2,7,1]
# 2    


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

        #(speed, effiency)
        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

from heapq import heappop, heappush

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


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.heappop(heap)
                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)
            else:
                if 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)
            


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] % mod, speed[i] % mod) for i in range(n)])
        maxi = 0
        others = PriorityQueue()
        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

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] % mod, speed[i] % mod) 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

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)
            else:
                sum_spd += spd - heapq.heappushpop(arr, spd)
            res = max(res, sum_spd*eff)
        return res % (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

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
    
    
    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)
        speed_h = []
        speed_sum = 0
        max_perf = 0
        for e, s in eff_speed:
            heapq.heappush(speed_h, s)
            speed_sum += s
            if len(speed_h) > k:
                speed_sum -= heapq.heappop(speed_h)
            max_perf = max(max_perf, speed_sum * e)
        return max_perf % mod
            


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:
    # O(nlogn + 2nlogk) time, no unnecessary max comparison, O(n) space
    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
    
    # O(nlogn + 2nlogk) time, O(n) space
    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)
        speed_h = []
        speed_sum = 0
        max_perf = 0
        for e, s in eff_speed:
            heapq.heappush(speed_h, s)
            speed_sum += s
            if len(speed_h) > k:
                speed_sum -= heapq.heappop(speed_h)
            max_perf = max(max_perf, speed_sum * e)
        return max_perf % mod
            


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:  # always add this eng.
                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


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 % ((10**9) + 7)

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])  # sort by efficiency in decreasing order

        performance = 0
        tot_speed = 0
        for engineer in engineers:
            min_efficiency = engineer[1]
            if len(pq) == k:
                if pq[0] < engineer[0]:  # if there's an engineer with higher speed, there's a good chance to get higher performance
                    bad_speed = heapq.heappop(pq)  # fire the guy with the lowest speed
                    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, speed, efficiency, k):
        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)



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)