CF2144D Price Tags

假设你是一家商店的老板。为了新一季到来之前清理库存，你决定举行一次全面大促销。 你的店里有 $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$），表示每件商品的原始价格。

对于每个测试用例，输出一个整数，表示最大总收入。

在第一个测试用例中，最优选择 $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$，新价格与原价完全相同，因此不需要新标签。 由 ChatGPT 5 翻译