<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>

#define ll long long
bool compare(pair<ll,ll> p1,pair<ll,ll> p2)
{
    return p1.second < p2.second; 
}
class Solution {
public:

    int maxPerformance(int n, vector<int>& a, vector<int>& b, int k) 
    {
        const ll mod = 1000000007;

        multiset<ll> big;
        multiset<ll> small;

        vector<pair<ll,ll>> v;
        for(int i =0;i<n;i++)
        {
            v.push_back({a[i],b[i]});
        }
        sort(v.begin(),v.end(),compare);
        // ll n = a.size();
        ll bsum = 0;
        for(int i =0;i<n;i++)
        {
            big.insert(a[i]);
            bsum += a[i];
            if(big.size() > k)
            {
                ll el = *big.begin();
                big.erase(big.find(el));
                small.insert(el);
                bsum -= el;
            }
        }

        ll ans = ((ll)(v[0].second)) * bsum;
        

        for(int i =1;i<n;i++)
        {
            if(big.find(v[i - 1].first) != big.end())
            {
                big.erase(big.find(v[i -1].first));
                bsum -= v[i -1].first;
            }
            else
            {
                small.erase(small.find(v[i-1].first));
            }

            // if(v[i].second == v[i - 1].second)
            // {
            //     continue;
            // }   

            while(big.size() < k && small.size() > 0)
            {
                ll el = *small.rbegin();
                big.insert(el);
                bsum += el;
                small.erase(small.find(el));
            }
            while(big.size() > 0 && small.size() > 0 && (*small.rbegin() > *big.begin()))
            {
                ll b =  *big.begin();
                ll s = *small.rbegin();
                big.erase(big.find(b));
                small.erase(small.find(s));

                big.insert(s);
                small.insert(b);

                bsum += s - b;
            }
            // for(auto it : big)
            // {
            //     cout << it << " ";
            // }
            // cout << endl;

            // for(auto it : small)
            // {
            //     cout << it << " ";
            // }
            // cout << endl;

            // cout << bsum << endl;

            ans = max(ans,((ll)(v[i].second)) * bsum);
        }

        return ans%mod;

    }
};
51871