K Smallest Sum Pairs

You are given two lists of integers nums1 and nums2, both sorted in non-decreasing order, and an integer k.

Consider every pair made of one element of nums1 and one element of nums2. A pair is identified by its indices (i, j) and has the sum nums1[i] + nums2[j].

Order the pairs by sum from smallest to largest. Break ties by smaller i, then by smaller j.

Return the first k pairs in this order, each written as [nums1[i], nums2[j]].

You can assume k is at most the number of pairs.

Examples

Example 1

Input:  nums1 = [1, 7, 11]
        nums2 = [2, 4, 6]
        k     = 3
Output: [[1, 2],
         [1, 4],
         [1, 6]]
Explanation: The pair sums in order are 3, 5, 7 (all with 1 from nums1), then 9 for [7,2]. The first three pairs are [1,2], [1,4], and [1,6].

Example 2

Input:  nums1 = [1, 1, 2]
        nums2 = [1, 2, 3]
        k     = 2
Output: [[1, 1],
         [1, 1]]
Explanation: The pairs (0, 0) and (1, 0) both have sum 2 and are the two smallest. They both read [1,1].