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

class Solution:
    #How do we use k-heaps here?
    #We obviously can't just check all possible combinations of (n choose k) subsequences when n, k are large
    #Can we use a prefix sum for num1?
    #Can we use a heap for num2?

    #Note we don't need to actually return the subsequence, just the maximum possible score ...

    #Well, if we start by getting the kth largest value of num2, we know any subsequence will have min(items in num2) at most equal to that, if not less.
        #But of course the sequence could entirely not select any of these num2 values and still have the highest score, if num1 is a lot larger at other indices.
    
    #Can we do this by induction?

    #What if we get the largest k items in num1? Still not enough ...

    #Let m_i = num1_i * num2_i, which is the largest possible contribution each index could have to the score (less if there's num2s with smaller value in the subsequence).
    

    
    #m = []
    #for i in range(n):
    #    m.append(nums1[i] * nums2[i])
    #print(m)
    #Then, ... even the k best here aren't enough. Hmm ...

    #Okay, induction. Let's say we have the best-score sequence length (k-1), with a given score s min(num2) value m.
    #Then for each potential n1i, n2i values, the best we can do to _add_ to the score it n1i * n2i, while we reduce the score by s * max(0, m - n2i)
    #But is this 'greedy' (increasing k) solution actually the global best?
        # Assume not: remove some set {q} of indices and add {r} to get the global best
            #If new index i was removed:
            #If not: 


    #What if we consider the indices of largest k num1 and those of largest k num2 ... does that bracket anything? Nope:
    #[100, 11, 1] and [1, 11, 110]: with k = 1, index 1 has the highest score of (100, 121, 110) but the second-highest num1 and second-highest num2.
    def argsort(seq, reverse = False):
        return sorted(range(len(seq)), key = lambda index : seq[index], reverse = reverse)
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        import heapq
        n = len(nums1)
        sort_indices = Solution.argsort(nums2, reverse = True)
        vals = list(map(lambda i : nums1[i], sort_indices))
        mults = list(map(lambda i : nums2[i], sort_indices))
        heap = list(vals[:k]) # must copy
        heapq.heapify(heap)
        current_highest_num1_sum = sum(vals[:k])
        best_score = current_highest_num1_sum * mults[k-1]
        for i in range(k, n):
            val, mult = vals[i], mults[i]
            smallest_value_ejected = heapq.heappushpop(heap, val)
            current_highest_num1_sum += val - smallest_value_ejected
            best_score = max(best_score, mult * current_highest_num1_sum)
        return best_score
33875