<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 {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {

    //    10 + 5 + 2  * 4

    //    2 8
    //    3 3
    //    4 1
    //    5 2
    //    7 5
    //    9 3
       
      //  Time Complexity: O(N * (logN + logK)) 



      //sare combinations ke perofrmance calculate ho jaenge

      //make a candidates pair array so that we can osrt it in decreasing efficieny

      int MOD = 1e9 + 7;
      vector <pair< int, int>> candidates(n);

      for(int i=0; i< n; i++){
        candidates.push_back( { efficiency[i], speed[i]});
      }

      sort( candidates.rbegin(),  candidates.rend() );


    //   we need max k engg so make a PQ of size k and store speed and if size of pQ exceeds k then start popping(
    //      aturrally lowest speed engg will get popped out

     //make a min heap pq
     
     long long speedSum =0 , performance = INT_MIN ;
      priority_queue < int , vector<int>, greater<int> > pq;

      for (int i = 0; i < candidates.size(); ++i) {
        int s = candidates[i].second;
        int e = candidates[i].first;

        speedSum += s;

        pq.push( s);

        //so basically har k group engg ka performance calculate kr rhe and jab koi new engg ka bari hoga toh pq se sabse low speed wala engg pop ho jaega

        if( pq.size() > k){
            // who to remove? of course the one with smallest speed
            speedSum-= pq.top();
            pq.pop();
        }
         
        //direclty efficiency se multiply kr rhe as efficiency decreasing way me sorted hai, when you're at current posn i, then that position effi. is the min abhitak toh directly speed ka sum se sse multiply kr dena
        cout<< speedSum <<" " << e << endl;
        performance= max( performance, speedSum * e);

}

    return performance % MOD;

    }
};
44509