Вы являетесь главой большой фирмы. \(n\) человек работают на вас, и \(n\) нечетно (т.е. \(n\) не делится на \(2\)).
Вам нужно распределить зарплаты вашим работникам. У вас есть \(s\) долларов для этого, и \(i\)-й работник должен получить зарплату от \(l_i\) до \(r_i\) долларов. Вам нужно так распределить зарплаты, чтобы максимизировать медианную зарплату.
Чтобы найти медиану множества нечетного размера, вам нужно отсортировать все числа множества и взять то, которое находится ровно посередине. Например:
- медиана множества \([5, 1, 10, 17, 6]\) равна \(6\),
- медиана множества \([1, 2, 1]\) равна \(1\).
Гарантируется, что вам хватит денег для выплаты минимальных зарплат, т.е. \(l_1 + l_2 + \dots + l_n \le s\).
Обратите внимание, что вам не обязательно тратить все \(s\) долларов на зарплаты.
Вам нужно ответить на \(t\) тестовых наборов.
Выходные данные
На каждый набор выведите одно число — максимальную медианную зарплату, которую вы можете получить.
Примечание
В первом наборе вы можете распределить зарплаты следующим образом: \(sal_1 = 12, sal_2 = 2, sal_3 = 11\) (\(sal_i\) равно зарплате \(i\)-го работника). Тогда медианная зарплата будет равна \(11\).
Во втором наборе вам нужно платить \(1337\) долларов единственному работнику.
В третьем наборе вы можете распределить зарплаты следующим образом: \(sal_1 = 4, sal_2 = 3, sal_3 = 6, sal_4 = 6, sal_5 = 7\). Тогда медианная зарплата будет равна \(6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
11
1337
6
|