CF1928D Lonely Mountain Dungeons

曾经，中土世界的人类、精灵、矮人以及其他居民们聚集在一起，准备夺回被史矛革夺走的宝藏。为了这个伟大的目标，他们团结在强大的精灵 Timothy 周围，开始策划推翻孤山统治者的计划。 中土世界居民的军队将由若干小队组成。已知每一对属于同一族群、但分在不同小队的生物，会为军队的总战斗力增加 $b$ 单位。但由于 Timothy 难以指挥过多的小队，若军队由 $k$ 个小队组成，则总战斗力会减少 $(k-1) \cdot x$ 单位。注意，军队至少由一个小队组成。 已知中土世界共有 $n$ 个种族，第 $i$ 个种族的生物数量为 $c_i$。请帮助中土世界的居民们确定他们能够组建的军队的最大战斗力。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$b$ 和 $x$（$1 \le n \le 2 \cdot 10^5$，$1 \le b \le 10^6$，$0 \le x \le 10^9$），分别表示种族数和题目中描述的常数 $b$、$x$。 每个测试用例的第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le 2 \cdot 10^5$），表示每个种族的生物数量。 保证所有测试用例中 $c_1 + c_2 + \ldots + c_n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示中土世界居民能够组建的军队的最大战斗力。

在第一个测试用例中，中土世界的居民可以组建 $3$ 个小队。由于 $x = 0$，军队的战斗力不会因小队数量而减少。居民们可以按如下方式分配到各个小队： - 第一族的唯一代表分配到第一个小队。 - 第二族的第一个代表分配到第一个小队，第二个代表分配到第二个小队。这样军队的总战斗力增加 $b = 1$。 - 第三族的第一个代表分配到第一个小队，第二个代表分配到第二个小队，第三个代表分配到第三个小队。这样军队的总战斗力增加 $3 \cdot b = 3$，因为他们在不同小队中形成了三对。 因此，总战斗力为 $4$。 在第二个测试用例中，中土世界的居民可以组建 $3$ 个小队。由于 $x = 10$，军队的战斗力会减少 $20$。居民们可以按如下方式分配到各个小队： - 第一族的第一个代表分配到第一个小队，第二个代表分配到第二个小队。这样军队的总战斗力增加 $b = 5$。 - 第二族的第一个和第二个代表分配到第一个小队，第三个和第四个代表分配到第二个小队，第五个代表分配到第三个小队。这样军队的总战斗力增加 $8 \cdot b = 40$。 - 第三族的第一个代表分配到第一个小队，第二个代表分配到第二个小队，第三个代表分配到第三个小队。这样军队的总战斗力增加 $3 \cdot b = 15$，因为他们在不同小队中形成了三对。 因此，总战斗力为 $5 + 40 + 15 - 20 = 40$。 由 ChatGPT 4.1 翻译