CF2144D.Price Tags

Imagine that you are the owner of a store. Before the start of a new season, you decided to clear your store of leftover goods, and therefore you decided to hold a total sale.

You have $n$ different items in your store: the $i$-th item costs $c_i$ coins. Each item has a price tag with the corresponding price $c_i$. You decided to hold a sale in the format: "we divided all the prices $x$ times." Formally, this means that you choose a common coefficient $x$, and during the sale, the $i$-th item will cost $\left\lceil \frac{c_i}{x} \right\rceil$ coins (where $\left\lceil y \right\rceil$ denotes rounding up).

To avoid confusion among the customers, you need to pin new price tags with new prices on all items, but printing new price tags is costly. Specifically, each printed price tag will cost you $y$ coins.

Therefore, you had a brilliant idea — why not use the existing price tags and simply repin them on other items? So, you'll need to print price tags only for those items that do not have a corresponding price tag available.

There remains one last question: by how much should you reduce the prices, or what $x$ should you choose? The coefficient $x$ must be an integer strictly greater than $1$ and such that the total income is maximized. The total income is equal to the total value of the items minus the cost of the printed price tags.

Determine the maximum possible total income.

假设你是一家商店的店主。在新一季开始之前，你决定清空店内剩余商品，因此决定举行一场全场大促销。

你的商店中有 $n$ 种不同的商品：第 $i$ 种商品售价为 $c_i$ 枚金币。每件商品都贴有一张标有对应价格 $c_i$ 的价签。你决定以“所有价格统一除以 $x$”的形式开展促销。形式化地说，这意味着你选择一个公共系数 $x$，而在促销期间，第 $i$ 种商品的售价将变为 $\left\lceil \frac{c_i}{x} \right\rceil$ 枚金币（其中 $\left\lceil y \right\rceil$ 表示对 $y$ 向上取整）。

为避免顾客混淆，你需要为所有商品贴上标有新价格的新价签；但印刷新价签成本较高：每张新印制的价签需花费你 $y$ 枚金币。

因此，你产生了一个绝妙的想法——何不重复利用现有价签，仅将其重新粘贴到其他商品上？换言之，你只需为那些没有现成对应价格价签的商品印刷新价签。

最后还剩一个问题：价格应降低多少，即应选择怎样的 $x$？系数 $x$ 必须是严格大于 $1$ 的整数，且需使总收入最大化。总收入等于所有商品销售所得总额减去印刷新价签的成本。

请计算可能获得的最大总收入。

The first line contains a single integer $t$ ($1 \le t \le 10$) — the number of test cases.

The first line of each test case contains two integers $n$ and $y$ ($1 \le n \le 2 \cdot 10^5$; $1 \le y \le 10^9$) — the number of items and the cost of printing one price tag.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 2 \cdot 10^5$) — the initial prices of the items.

第一行包含一个整数 $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$）—— 各商品的初始价格。

For each test case, output a single integer — the maximum total income.

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

In the first test case, it is optimal to choose $x = 3$. The new prices of the items will be $[17, 50, 17, 50, 50]$. In this case, we can use two old price tags of $50$, and we will have to print three price tags for $17$, $17$, and $50$. As a result, the income will be $17 + 50 + 17 + 50 + 50 - 51 \cdot 3 = 31$.

In the second test case, it is optimal to choose $x = 2$. The new prices will be $[21, 21, 21]$, and we will have to print $3$ new price tags.

In the third test case, it is optimal to choose $x = 111$.

In the fourth test case, it is optimal to choose $x = 2$. The new prices will be the same as the old ones, so no new price tags will be printed.

在第一个测试用例中，选择 $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$ 是最优的。新价格与原价格完全相同，因此无需打印任何新价签。