The Deli's Hamper Price List

A deli sells n items with prices prices. A hamper is any non-empty set of different items, and its price is the sum of the prices inside it. Items are told apart by position, so two hampers holding different items count as different hampers even when their prices are equal.

The deli prints a price list of all 2**n - 1 hampers from cheapest to dearest. Return the price on line k (line 1 is the cheapest hamper).

Examples

Input:  prices = [3, 1, 2], k = 4
Output: 3
Explanation: the hampers cost 1, 2, 3, 1+2, 1+3, 2+3 and 1+2+3, so the sorted
             list is 1, 2, 3, 3, 4, 5, 6 and line 4 shows 3.

Input:  prices = [3, 1, 2], k = 7
Output: 6

Constraints

• 1 <= n = len(prices) <= 2 * 10**5
• 0 <= prices[i] <= 10**6
• 1 <= k <= min(2**n - 1, 2 * 10**5)
• Listing every hamper is hopeless for large n, and so is keeping a list of the k cheapest sums up to date item by item.

Goals

• Enumerate an exponential family of choices in increasing order without listing it
• Give every choice exactly one parent that is never more expensive
• Pop only k items from a heap that grows by at most two per pop