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$$$-го цветка в магазине.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot {10}^5$$$.
Для каждого набора входных данных выведите одно целое число — максимально возможное количество лепестков в букете, который может собрать девочка, соблюдая все перечисленные выше условия.
55 101 1 2 2 38 204 2 7 5 6 1 1 18 100000239 30 610 122 24 40 8 211 132 4 11 1 1 2 3 5 4 3 28 1033206 206 206 207 207 207 207 1000
7 13 610 13 1033
В первом наборе входных данных вы можете собрать букет из $$$(1, 1, 2, 2), (2, 2, 3), (1, 1), (2, 2)$$$. Максимум из разрешенных букетов, не превышающий $$$10$$$, составляет $$$7$$$ для $$$(2, 2, 3)$$$. В третьем наборе входных данных вы можете собрать букет из одного цветка любого типа, поэтому ответ — $$$610$$$. В четвертом наборе входных данных вы можете собрать букет из $$$(4, 4, 5)$$$, что даст вам $$$13$$$ лепестков, и это максимальное количество лепестков, которое может купить девочка.
Название |
---|