Codeforces Round 961 (Div. 2) |
---|
Закончено |
Это сложная версия задачи. Единственное отличие в том, что в этой версии вместо перечисления количеств лепестков у каждого цветка задано для всех типов цветов (по количеству лепестков) их количество в магазине.
Девочка готовится к своему дню рождения и хочет составить невероятной красоты букет. В магазине представлено в общей сложности $$$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$$$.
Для каждого набора входных данных выведите одно целое число — максимально возможное количество лепестков в букете, который может собрать девочка, соблюдая все перечисленные выше условия.
73 101 2 32 2 13 1033206 207 10003 4 16 204 2 7 5 6 11 2 1 3 1 78 100000239 30 610 122 24 40 8 212 13123 112 1456 124 100 123 109826 132 4 11 1 3 52 2 1 2 2 18 10330206 210 200 201 198 199 222 10009 10 11 12 13 14 15 162 1000000000011 1287312315 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$$$ лепестков.
Название |
---|