B2. Букет (сложная версия)
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие в том, что в этой версии вместо перечисления количеств лепестков у каждого цветка задано для всех типов цветов (по количеству лепестков) их количество в магазине.

Девочка готовится к своему дню рождения и хочет составить невероятной красоты букет. В магазине представлено в общей сложности $$$n$$$ различных типов цветов, для каждого из перечисленных типов цветов указано их количество в магазине. Цветок с $$$k$$$ лепестками стоит $$$k$$$ монет. Девочка решила, что разница в количестве лепестков между любыми двумя цветами, которые она будет использовать для составления букета, не должна превышать единицы. В то же время девочка хочет собрать букет с максимально возможным количеством лепестков. К сожалению, у неё есть только $$$m$$$ монет, и она не может потратить больше. С каким максимальным количеством лепестков она может собрать букет?

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

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

Первая строка каждого тестового примера содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^{18}$$$) — количество типов цветов в магазине и количество монет у девочки. Вторая строка каждого тестового примера содержит $$$n$$$ целых различных чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ – это количество лепестков у $$$i$$$-го типа цветов в магазине (для различных индексов $$$i \neq j$$$ гарантируется, что количество лепестков у соответствующих типов цветов различное, то есть $$$a_i \neq a_j$$$). Третья строка каждого тестового примера содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$), где $$$c_i$$$ – количество цветов $$$i$$$-го типа в магазине.

Сумма $$$n$$$ по всем тестовым случаям не превышает $$$2 \cdot {10}^5$$$.

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

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

Пример
Входные данные
7
3 10
1 2 3
2 2 1
3 1033
206 207 1000
3 4 1
6 20
4 2 7 5 6 1
1 2 1 3 1 7
8 100000
239 30 610 122 24 40 8 2
12 13123 112 1456 124 100 123 10982
6 13
2 4 11 1 3 5
2 2 1 2 2 1
8 10330
206 210 200 201 198 199 222 1000
9 10 11 12 13 14 15 16
2 10000000000
11 12
87312315 753297050
Выходные данные
7
1033
19
99990
13
10000
9999999999
Примечание

В первом наборе входных данных некоторые разрешенные букеты — это $$$(1, 1, 2, 2), (2, 2, 3), (1, 1), (2, 2)$$$. Максимум из разрешенных букетов, не превышающий $$$10$$$, составляет $$$7$$$ для $$$(2, 2, 3)$$$. Во втором наборе входных данных вы можете собрать разрешенный букет из $$$(206, 206, 207, 207, 207)$$$ с суммой $$$1033$$$, что является максимальным количеством лепестков, которое может купить девушка. В третьем наборе входных данных вы можете собрать корректный букет из $$$(5, 5, 5, 4)$$$ с суммой $$$19$$$. Видно, что ни в одном разрешенном букете не может быть $$$20$$$ лепестков.