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

    def __init__(self):
        self._heap: List[int] = [-1]
        self.size: int = 0

    def heap_push(self, num: int):
        self.size += 1
        self._heap.append(num)

        cur_p = self.size

        while cur_p > 1:
            par_p = cur_p >> 1

            if self._heap[par_p] <= self._heap[cur_p]:
                break
            self._swap(par_p, cur_p)
            cur_p = par_p

    def heap_pop(self) -> int | None:
        if self.size <= 0:
            return None
        min_elem = self._heap[1]

        self._swap(1, self.size)
        self._heap.pop()
        self.size -= 1

        cur_p = 1

        while (cur_p << 1) + 1 <= self.size:

            left_p, right_p = (cur_p << 1), (cur_p << 1) + 1

            min_val = min(self._heap[cur_p], self._heap[left_p], self._heap[right_p])

            if min_val == self._heap[cur_p]:
                break
            elif min_val == self._heap[left_p]:
                self._swap(cur_p, left_p)
                cur_p = left_p
            elif min_val == self._heap[right_p]:
                self._swap(cur_p, right_p)
                cur_p = right_p

        if (cur_p << 1) <= self.size and self._heap[cur_p] > self._heap[cur_p << 1]:
            self._swap(cur_p, cur_p << 1)

        return min_elem

    def _swap(self, idx1: int, idx2: int) -> None:

        self._heap[idx1], self._heap[idx2] = self._heap[idx2], self._heap[idx1]

    def peek(self) -> int | None:

        return self._heap[1] if self.size > 0 else None


class MaxScoreSolution:
    def __init__(self, nums1: List[int], nums2: List[int], k: int):
        self.nums1: List[int] = nums1
        self.nums2: List[int] = nums2
        self.k: int = k

    def solve(self) -> int:

        pairs = sorted(zip(self.nums1, self.nums2), key=itemgetter(1), reverse=True)

        min_heap: MinHeap = MinHeap()

        cur_sum = 0
        obj_score = 0

        for i in range(len(pairs)):
            ui, vi = pairs[i]

            cur_sum += ui
            min_heap.heap_push(ui)

            if i >= self.k-1:
                obj_score = max(obj_score, cur_sum * vi)
                cur_sum -= min_heap.heap_pop()

        return obj_score

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        sln = MaxScoreSolution(nums1, nums2, k)

        return sln.solve()
37325