<p>There are two mice and <code>n</code> different types of cheese, each type of cheese should be eaten by exactly one mouse.</p>

<p>A point of the cheese with index <code>i</code> (<strong>0-indexed</strong>) is:</p>

<ul>
	<li><code>reward1[i]</code> if the first mouse eats it.</li>
	<li><code>reward2[i]</code> if the second mouse eats it.</li>
</ul>

<p>You are given a positive integer array <code>reward1</code>, a positive integer array <code>reward2</code>, and a non-negative integer <code>k</code>.</p>

<p>Return <em><strong>the maximum</strong> points the mice can achieve if the first mouse eats exactly </em><code>k</code><em> types of cheese.</em></p>

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

<pre>
<strong>Input:</strong> reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
<strong>Output:</strong> 15
<strong>Explanation:</strong> In this example, the first mouse eats the 2<sup>nd</sup>&nbsp;(0-indexed) and the 3<sup>rd</sup>&nbsp;types of cheese, and the second mouse eats the 0<sup>th</sup>&nbsp;and the 1<sup>st</sup> types of cheese.
The total points are 4 + 4 + 3 + 4 = 15.
It can be proven that 15 is the maximum total points that the mice can achieve.
</pre>

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

<pre>
<strong>Input:</strong> reward1 = [1,1], reward2 = [1,1], k = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> In this example, the first mouse eats the 0<sup>th</sup>&nbsp;(0-indexed) and 1<sup>st</sup>&nbsp;types of cheese, and the second mouse does not eat any cheese.
The total points are 1 + 1 = 2.
It can be proven that 2 is the maximum total points that the mice can achieve.
</pre>

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

<ul>
	<li><code>1 &lt;= n == reward1.length == reward2.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= reward1[i],&nbsp;reward2[i] &lt;= 1000</code></li>
	<li><code>0 &lt;= k &lt;= n</code></li>
</ul>

# in: int[] reward1, int[] reward2, int k
# out: max combined sum of k els from reward1 and (n - k) els from reward2

# we could try every combo (O(N^2))
# we could pick the optimal sum without the k restriction
# we can also have the diff between mouse1 and mouse2
# finally, we increase/decrease the smallest diffs to get us to k
# T: O(NlogN)
# S: O(N)

# OR maximize diffs, pick k items where mouse1 is much better than mouse2
# populate teh remainder from mouse2, but don't include ones that mouse1 as taken
# T: O(NlogK)
# S: O(N)

import heapq
class Solution:
    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
        if not reward1 or not reward2:
            return 0

        best_sum = 0
        mouse1_meals = 0
        mouse1_better = []
        mouse2_better = []
        for i in range(len(reward1)):
            if reward1[i] >= reward2[i]:
                best_sum += reward1[i]
                mouse1_meals += 1
                mouse1_better.append(reward1[i] - reward2[i])
            else:
                best_sum += reward2[i]
                mouse2_better.append(reward2[i] - reward1[i])

        heapq.heapify(mouse1_better)
        heapq.heapify(mouse2_better)

        while mouse1_meals < k:
            switch = heapq.heappop(mouse2_better)
            mouse1_meals += 1
            best_sum -= switch
        
        while mouse1_meals > k:
            switch = heapq.heappop(mouse1_better)
            mouse1_meals -= 1
            best_sum -= switch
        
        return best_sum

        # below we keep the heap to size k
        # if not reward1 or not reward2:
        #     return 0
        # heap = []
        # result = 0
        # occupied = set()

        # for i in range(len(reward1)):
        #     diff = reward1[i] - reward2[i]
        #     heapq.heappush(heap, (diff, i))
        #     if len(heap) > k:
        #         heapq.heappop(heap)
        
        # while heap:
        #     item = heapq.heappop(heap)
        #     result += reward1[item[1]]
        #     occupied.add(item[1])

        # for i in range(len(reward2)):
        #     if i not in occupied:
        #         result += reward2[i]

        # return result
447