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

import heapq

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        """
        Given two synced lists, we're trying to find the best collection of
        indices where we have `k` number of values. In `nums1` we sum those
        values, to then multiply by the minimum value of `nums2`. We're looking
        for the highest product possible between these lists.

        Args:
            `nums1`: A first list of non-negative integers.
            `nums2`: A second list of non-negative integers.
        Returns:
            `max_product`: A maximum found product.
        """

        def sort_the_lists(a: list[int], b: list[int]) -> list:
            """
            Sort the lists together with the second list being from largest to
            smallest.
            """
            # a = [4, 2, 3, 1, 1]
            # b = [7, 5, 10, 9, 6]
            # output = [[3, 10], [1, 9], [4, 7], [1, 6], [2, 5]]
            return [
                [x, y] for x, y in sorted(zip(a, b), key=lambda i: i[1], reverse=True)
            ]

        # Handle edge-case.
        if k == 1:
            max_product = 0
            for i in range(len(nums1)):
                temp = nums1[i] * nums2[i]
                if temp > max_product:
                    max_product = temp
            return max_product

        # Sort the lists.
        zipped = sort_the_lists(nums1, nums2)

        # Build an initial list of max-sum-values in a list.
        # Keep a note on the sum of that list, if it changes.
        max_product = 0
        max_values = []
        # lowest_value = zipped[0][0]
        # test = [0] * (k - 1)
        max_values_sum = 0
        for j in range(0, k - 1):
            heapq.heappush(max_values, zipped[j][0])
            max_values_sum += zipped[j][0]
        # lowest_value = heapq.nsmallest(1, max_values)[0]
        # lowest_value = max_values[0]
        max_product = (zipped[k - 1][0] + sum(max_values)) * zipped[k - 1][1]
        # test.append(max_product)

        # Iterate through the list generating best products as we go.
        for i in range(k, len(zipped)):
            heapq.heappush(max_values, zipped[i - 1][0])
            max_values_sum -= heapq.heappop(max_values)
            max_values_sum += zipped[i - 1][0]

            max_product = max(max_product, (zipped[i][0] + max_values_sum) * zipped[i][1])
        return max_product
43325