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.

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.

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.