All problems

The Kth Cheapest Meal

Hard · binary search

A canteen sells a meal as one main dish plus one side dish. mains lists the prices of the main dishes and sides lists the prices of the side dishes, both in pence and both in ascending order. Every main can be paired with every side, and the price of a meal is the price of its main plus the price of its side.

Two different pairings are two different meals, even when their prices are equal. Imagine all the meals written out from the cheapest to the most expensive (equal prices in any order). Return the price of the k-th meal in that list, counting from 1.

The number of meals can be too large to write out in full.

Examples

Example 1

Input: mains = [1, 4, 7], sides = [2, 3, 10], k = 5

Output: 9

The meal prices in order are 3, 4, 6, 7, 9, 10, 11, 14, 17. The 5th one is 9.

Example 2

Input: mains = [5, 5], sides = [5, 5], k = 3

Output: 10

All four meals cost 10.

Constraints

• 1 <= len(mains), len(sides) <= 10^5
• 1 <= mains[i], sides[j] <= 10^9
• mains and sides are sorted in ascending order (equal values allowed).
• 1 <= k <= len(mains) * len(sides)