Представьте, что вы — владелец магазина. Перед началом нового сезона вы решили очистить свой магазин от остатков товара, и потому вы решили устроить тотальную распродажу.
Всего у вас в магазине $$$n$$$ различных товаров: $$$i$$$-й товар стоит $$$c_i$$$ монет. На каждом товаре висит ценник с соответствующей ценой $$$c_i$$$. Вы решили устроить распродажу в формате: «делим цены в $$$x$$$ раз». Формально это значит, что вы выбираете общий коэффициент $$$x$$$ и во время распродажи $$$i$$$-й товар будет стоить $$$\left\lceil \frac{c_i}{x} \right\rceil$$$ монет (где $$$\left\lceil y \right\rceil$$$ означает округление вверх).
Для того чтобы покупатели не запутались, вам нужно повесить на все товары ценники с новой ценой, но печатать новые ценники затратно. А именно, каждый напечатанный ценник будет стоить вам $$$y$$$ монет.
Поэтому вас постигла гениальная идея — а почему бы не использовать уже существующие ценники и просто перевесить их на другие товары? А ценники напечатать только для тех товаров, которым не хватает соответствующего ценника.
Остался последний вопрос: во сколько раз снизить цену, или же какой $$$x$$$ выбрать. Коэффициент $$$x$$$ должен быть целым числом строго больше $$$1$$$ и таким, чтобы общий доход был максимальным. Общий доход равен суммарной стоимости товаров минус стоимость напечатанных ценников.
Определите максимально возможный общий доход.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных.
В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$y$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le y \le 10^9$$$) — количество товаров и цена печати одного ценника.
Во второй строке заданы $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 2 \cdot 10^5$$$) — первоначальные цены товаров.
Для каждого набора входных данных выведите одно целое число — максимальный общий доход.
45 5150 150 50 148 1503 100000000042 42 4210 543211 8088 45 1 73 1 9198 4991 1 833 1001 1 1
31-2999999937-1627553
В первом наборе входных данных выгодно выбрать $$$x = 3$$$. Новые цены товаров станут равны $$$[17, 50, 17, 50, 50]$$$. В таком случае мы сможем использовать два старых ценника по $$$50$$$, а еще три ценника на $$$17$$$, $$$17$$$ и $$$50$$$ придется напечатать. В результате доход будет равен $$$17 + 50 + 17 + 50 + 50 - 51 \cdot 3 = 31$$$.
Во втором наборе выгодно выбрать $$$x = 2$$$. Новые цены будут равны $$$[21, 21, 21]$$$, и нам придется напечатать $$$3$$$ новых ценника.
В третьем наборе выгодно выбрать $$$x = 111$$$.
В четвертом наборе выгодно выбрать $$$x = 2$$$. Новые цены будут равны старым, поэтому новые ценники не потребуются.
