Cheapest Meal Combos

A café sells a main course and a drink as a combo. You have the prices of the mains and the prices of the drinks, each list sorted from cheapest to dearest. A combo is one main plus one drink, and its price is the sum of the two prices.

Write cheapest_combos(mains, drinks, k) that returns the prices of the k cheapest combos, as a list sorted from lowest to highest. Every pairing of a main with a drink is its own combo, so the same price can appear more than once. If there are fewer than k combos in total, return the prices of all of them.

Examples

cheapest_combos([3, 5, 9], [1, 2, 6], 4)
# returns [4, 5, 6, 7]

cheapest_combos([2, 2], [1, 3], 3)
# returns [3, 3, 5]

cheapest_combos([4], [1, 2], 10)
# returns [5, 6]

In the first example the four cheapest combos are 3 + 1, 3 + 2, 5 + 1 and 5 + 2.

Constraints

• 0 <= len(mains), len(drinks) <= 100,000, and both lists are sorted from lowest to highest
• Prices are whole numbers from 1 to 10^9
• 0 <= k <= 100,000
• There can be 10 billion combos, far too many to list: the answer has to come from looking at only a small part of them.