Salary Changing - Titan Online Assessment

Problem Preview

"Level : Codeforces Div-2 D You are managing a company with `n` employees, where `n` is guaranteed to be odd. You have a total budget of `s` dollars to distribute as salaries. For every employee `i`, their salary must be chosen within the range `[l_i, r_i]`. Your task is to assign a valid salary to every employee such that the **median salary is as large as possible**. For a sequence containing an odd number of elements, its median is the element located at the middle position after sorting the sequence in non-decreasing order. For example: * The median of `[5, 1, 10, 17, 6]` is `6`. * The median of `[1, 2, 1]` is `1`. It is guaranteed that the available budget is sufficient to give every employee their minimum possible salary: `l_1 + l_2 + ... + l_n ≤ s` You are **not required to use the entire budget**. ### Input The first line contains an integer `t` — the number of test cases. For each test case: * The first line contains two integers `n` and `s`, representing the number of employees and the total available budget. * The next `n` lines each contain two integers `l_i` and `r_i`, representing the minimum and maximum salary allowed for employee `i`. #### Constraints * `1 ≤ t ≤ 2 · 10^5` * `1 ≤ n < 2 · 10^5` * `n` is odd * `1 ≤ s ≤ 2 · 10^14` * `1 ≤ l_i ≤ r_i ≤ 10^9` * The sum of `n` over all test cases does not exceed `2 · 10^5` * `Σ l_i ≤ s` ### Output For every test case, print a single integer — the **maximum median salary** that can be achieved while satisfying all salary ranges and staying within the available budget. ### Example #### Input ```text 3 3 26 10 12 1 4 10 11 1 1337 1 1000000000 5 26 4 4 2 4 6 8 5 6 2 7 ``` #### Output ```text 11 1337 6 ``` ### Explanation In the first test case, one possible salary assignment is: `[12, 2, 11]` After sorting, it becomes `[2, 11, 12]`, so the median is `11`. In the second test case, there is only one employee, and their salary can be exactly `1337`, making the median `1337`. For the third test case, one valid assignment is: `[4, 3, 6, 6, 7]` After sorting, the median is `6`. Therefore, the maximum possible medians for the three test cases are `11`, `1337`, and `6`, respectively."