← 返回题目列表

Codeforces · 2144/D

D. 价格标签

中文机器翻译题面 查看原题

想象一下您是一家商店的老板。在新季节开始之前,您决定清理商店的剩余商品,因此决定进行全面促销。

您的商店中有 $$$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$$$) — 商品的初始价格。

输出

对于每个测试用例,输出一个整数 - 最大总收入。

示例

输入
复制

4
5 51
50 150 50 148 150
3 1000000000
42 42 42
10 54321
1 8088 45 1 73 1 9198 4991 1 83
3 100
1 1 1

输出
复制

31
-2999999937
-162755
3

注意

在第一个测试用例中,最佳选择 $$$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$$$。新价格将与旧价格相同,因此不会打印新的价格标签。