C. Выполните операции и максимизируйте счёт
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Я вижу хендл satyam343. У меня идут мурашки по телу. Пожалуйста, в этот раз больше задач про медианы. Я их обожаю. Пожалуйста, satyam343, мы верим в тебя.
— Самый большой поклонник satyam343

Вам дан массив $$$a$$$ длины $$$n$$$ и целое число $$$k$$$. Вам также дан бинарный массив $$$b$$$ длины $$$n$$$.

Вы можете выполнить следующую операцию не более $$$k$$$ раз:

  • Выбрать индекс $$$i$$$ ($$$1 \leq i \leq n$$$) такой, что $$$b_i = 1$$$. Установить $$$a_i = a_i + 1$$$ (т.е. увеличить $$$a_i$$$ на $$$1$$$).

Ваш счёт определяется как $$$\max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right)$$$, где $$$c_i$$$ обозначает массив длины $$$n-1$$$, который вы получаете, удаляя $$$a_i$$$ из $$$a$$$. Другими словами, ваш счёт — это максимальное значение $$$a_i + \operatorname{median}(c_i)$$$ среди всех $$$i$$$ от $$$1$$$ до $$$n$$$.

Найдите максимальный счёт, который можно получить при оптимальном выполнении операций.

Для произвольного массива $$$p$$$, $$$\operatorname{median}(p)$$$ определяется как $$$\left\lfloor \frac{|p|+1}{2} \right\rfloor$$$-й элемент в отсортированном $$$p$$$. Например, $$$\operatorname{median} \left( [3,2,1,3] \right) = 2$$$ и $$$\operatorname{median} \left( [6,2,4,5,1] \right) = 4$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Каждый набор входных данных начинается с двух целых чисел $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^9$$$) — длина $$$a$$$ и количество операций, которые вы можете выполнить.

Следующая строка содержит $$$n$$$ разделенных пробелом целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — массив $$$a$$$.

Следующая строка содержит $$$n$$$ разделенных пробелом целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$b_i$$$ равно $$$0$$$ или $$$1$$$) — массив $$$b$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите на отдельной строке максимальное значение счёт, которое вы можете получить.

Пример
Входные данные
8
2 10
3 3
1 1
3 10
3 3 3
0 0 0
4 4
2 1 5 1
0 1 0 1
5 4
7 5 2 5 4
0 0 1 0 1
5 1
5 15 15 2 11
1 0 0 1 1
5 2
10 11 4 10 15
1 1 0 1 0
4 4
1 1 2 5
1 1 0 0
2 1000000000
1000000000 1000000000
1 1
Выходные данные
16
6
8
13
21
26
8
3000000000
Примечание

Для первого набора входных данных оптимально выполнить $$$5$$$ операций над обоими элементами и получить $$$a = [8,8]$$$. Таким образом, максимальная оценка, которую мы можем получить, равна $$$\max(8 + \operatorname{median}[8], 8 + \operatorname{median}[8]) = 16$$$, так как $$$c_1 = [a_2] = [8]$$$. Можно доказать, что получить больший счёт невозможно.

Для второго набора входных данных вы не можете выполнить операции ни над одним элементом, поэтому $$$a$$$ остается $$$[3,3,3]$$$. Таким образом, максимальная оценка, которую мы можем получить, равна $$$3 + \operatorname{median}[3, 3] = 6$$$, так как $$$c_1 = [a_2, a_3] = [3, 3]$$$. Можно доказать, что получить больший счёт невозможно.