Maximize Median of Ranges

You are given a list of ranges ranges, where ranges[i] = [l, r], and an integer budget. The number of ranges is odd.

Choose one value v_i from each range, with l <= v_i <= r, so that the total of all chosen values is at most budget. You can assume that choosing every lower bound already fits the budget: the sum of ranges[i][0] over all i is at most budget.

Return the maximum possible median of the chosen values. With an odd count n, the median is the (n + 1) / 2-th smallest value among the n chosen values.

Examples

Example 1

Input: ranges = [[1,12],[1,2],[1,11]], budget = 25
Output: 11
Explanation: Choose 12, 2, 11 (total 25). The median is 11. Reaching a median of 12 would need two chosen values of at least 12, but only the first range can reach that high.

Example 2

Input: ranges = [[1,1000000000]], budget = 1337
Output: 1337
Explanation: With a single range, the median is the one chosen value, capped by the budget.