Find K Pairs with Smallest Sums

Statement

Given two lists, and an integer $k$, find $k$ pairs of numbers with the smallest sum so that in each pair, each list contributes one number to the pair.

Constraints:

• $1$ $\leq$ list1.length, list2.length $\leq$ $500$

• $-10^4$ $\leq$ list1[i], list2[i] $\leq$ $10^4$

• $1$ $\leq$ $k$ $\leq$ $10^3$

• Input lists should be sorted in ascending order.

• If the value of $k$ exceeds the total number of valid pairs that may be formed, return all the pairs.

Examples