<p>You are given two integers <code>n</code> and <code>k</code> and two integer arrays <code>speed</code> and <code>efficiency</code> both of length <code>n</code>. There are <code>n</code> engineers numbered from <code>1</code> to <code>n</code>. <code>speed[i]</code> and <code>efficiency[i]</code> represent the speed and efficiency of the <code>i<sup>th</sup></code> engineer respectively.</p>

<p>Choose <strong>at most</strong> <code>k</code> different engineers out of the <code>n</code> engineers to form a team with the maximum <strong>performance</strong>.</p>

<p>The performance of a team is the sum of its engineers&#39; speeds multiplied by the minimum efficiency among its engineers.</p>

<p>Return <em>the maximum performance of this team</em>. Since the answer can be a huge number, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
<strong>Output:</strong> 60
<strong>Explanation:</strong> 
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
<strong>Output:</strong> 68
<strong>Explanation:
</strong>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.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
<strong>Output:</strong> 72
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>speed.length == n</code></li>
	<li><code>efficiency.length == n</code></li>
	<li><code>1 &lt;= speed[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= efficiency[i] &lt;= 10<sup>8</sup></code></li>
</ul>

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

        # MOD = 10**9 + 7

        # speed_sorted_index = sorted(range(n), key = lambda x: speed[x])
        # efficiency_sorted_index = sorted(range(n), key = lambda x: efficiency[x])

        # # speed_sorted_index_dict = {}
        # # for i, key in enumerate(speed_sorted_index):
        # #     speed_sorted_index_dict[key] = i

        # productions = []
        # for i in range(n):

        #     ind = efficiency_sorted_index[i]
            
        #     min_efficiency = efficiency[ind] 
        #     min_efficiency_speed = speed[ind]

        #     index = speed_sorted_index.index(ind)
        #     # index = speed_sorted_index_dict[ind]

        #     del speed_sorted_index[index]
            
        #     sum_ = min_efficiency_speed

        #     m = k if i <= n-k else n-i
        #     for j in range(1, m):
        #         sum_ += speed[speed_sorted_index[-j]]

        #     production = sum_ * min_efficiency
            
        #     productions.append(production)

        # return max(productions) % MOD

        MOD = 10**9 + 7
        
        # Step 1: Pair efficiency and speed and sort by efficiency in descending order
        engineers = sorted(zip(efficiency, speed), key=lambda x: -x[0])
        
        # Step 2: Use a min-heap to keep the top k speeds
        speed_heap = []
        speed_sum = 0
        max_performance = 0
        
        # Step 3: Iterate through engineers sorted by efficiency
        for eff, spd in engineers:
            # Add the current engineer's speed to the heap
            heapq.heappush(speed_heap, spd)
            speed_sum += spd
            
            # If we have more than k engineers in the heap, remove the smallest speed
            if len(speed_heap) > k:
                speed_sum -= heapq.heappop(speed_heap)
            
            # Calculate the performance with the current engineer's efficiency
            performance = speed_sum * eff
            max_performance = max(max_performance, performance)
        
        # Step 4: Return the result modulo 10^9 + 7
        return max_performance % MOD
36100