from heapq import *
class Solution:
  def findKLargestPairs(self, nums1, nums2, k):

    heap = [(-nums1[0] - nums2[0], 0, 0)]
    result = []
    # every iteration, we add two elements and remove one.
    # we do k iterations.
    # thus the size of the heap is at most O(k)
    # Thus, this runtime is O(k log k)
    for _ in range(k):
      _,idx1, idx2 = heappop(heap)
      result.append([nums1[idx1], nums2[idx2]])
      if idx2 + 1 < len(nums2):
        heappush(heap, (-nums1[idx1] - nums2[idx2 + 1], idx1, idx2 + 1))
      if idx1 + 1 < len(nums1):
        heappush(heap, (-nums1[idx1 + 1] - nums2[idx2], idx1 + 1, idx2))

    return result