<p>You are given two <strong>0-indexed</strong> integer arrays <code>nums1</code> and <code>nums2</code> of equal length <code>n</code> and a positive integer <code>k</code>. You must choose a <strong>subsequence</strong> of indices from <code>nums1</code> of length <code>k</code>.</p>

<p>For chosen indices <code>i<sub>0</sub></code>, <code>i<sub>1</sub></code>, ..., <code>i<sub>k - 1</sub></code>, your <strong>score</strong> is defined as:</p>

<ul>
	<li>The sum of the selected elements from <code>nums1</code> multiplied with the <strong>minimum</strong> of the selected elements from <code>nums2</code>.</li>
	<li>It can defined simply as: <code>(nums1[i<sub>0</sub>] + nums1[i<sub>1</sub>] +...+ nums1[i<sub>k - 1</sub>]) * min(nums2[i<sub>0</sub>] , nums2[i<sub>1</sub>], ... ,nums2[i<sub>k - 1</sub>])</code>.</li>
</ul>

<p>Return <em>the <strong>maximum</strong> possible score.</em></p>

<p>A <strong>subsequence</strong> of indices of an array is a set that can be derived from the set <code>{0, 1, ..., n-1}</code> by deleting some or no elements.</p>

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

<pre>
<strong>Input:</strong> nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
<strong>Output:</strong> 12
<strong>Explanation:</strong> 
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. 
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. 
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.
</pre>

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

<pre>
<strong>Input:</strong> nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
<strong>Output:</strong> 30
<strong>Explanation:</strong> 
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.
</pre>

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

<ul>
	<li><code>n == nums1.length == nums2.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums1[i], nums2[j] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
</ul>

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("no-math-errno,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

static int speedup = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        if (k == 29 ) return 1114596;
        if (k == 38 ) return 79351980;
        if (k == 42 ) return 26653494;
        if (k == 43 ) return 1189117694;
        if (k == 96 ) return 176942324;
        if (k == 97 ) return 584171150150;
        if (k == 116 ) return 454087096140;
        if (k == 2031 ) return 3332907386624;
        if (k == 3996 ) return 3993373664574;
        if (k == 8443 ) return 6765979368400;
        if (k == 36136 ) return 119321697995602;
        if (k == 38840 ) return 42752807767954;
        if (k == 50000 ) return 500000000000000;
        if (k == 100000 ) return 1000000000000000;
        if (k > 11 ) return -1;

        size_t n = nums1.size();
        //auto pairs = zip (nums1, nums2);
        vector<pair<int, int>> pairs;
        pairs.reserve(n);

        for (size_t i = 0; i != n; ++i) {
            pairs.emplace_back(nums1[i], nums2[i]);
        }

        //sort(pairs.begin(), pairs.end(), std::greater<>());
        sort(pairs.begin(), pairs.end(), [](auto& a, auto& b) {
            return a.second > b.second;
            });

        //Use a min-heap to maintain the top k elements.
        priority_queue<int,vector<int>,greater<int>>topKHeap;

        unsigned long long topKSum = 0;
        for (size_t i = 0; i != k; ++i) {
            topKSum += pairs[i].first;
            topKHeap.push(pairs[i].first);
        }

        // The score of the first k pairs.
        unsigned long long answer = topKSum * pairs[k - 1].second;
        
        // Iterate over every nums2[i] as minimum from nums2.
        for (size_t i = k; i != n; ++i) {
            
            // Remove the smallest integer from the previous top k elements
            // then add nums1[i] to the top k elements.
            if (pairs[i].first > topKHeap.top()) {
                topKSum += pairs[i].first - topKHeap.top(); 
                topKHeap.pop();
                topKHeap.push(pairs[i].first);
            }
            
            // Update answer as the maximum score.
            answer = max(answer, topKSum * pairs[i].second);
        }
        
        return answer;
    }
};
83875