← 返回题目列表

Codeforces · 1928/D

D. 孤山地下城

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

曾经,中土世界的人民、精灵、矮人和其他居民聚集在一起,想要夺回被史毛格偷走的宝藏。以这个伟大目标的名义,他们团结在强大的精灵蒂莫西周围,开始策划推翻孤山的统治者。

中土居民的军队将由多个小队组成。众所周知,在不同小队中的每一对同一种族的生物都会为军队的总兵力增加 $$$b$$$ 个单位。但由于蒂莫西很难领导一支由大量小队组成的军队,因此由 $$$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$$$) — 每个 $$$n$$$ 种族的生物数量。

保证所有测试用例的值 $$$c_1 + c_2 + \ldots + c_n$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——中土世界居民可以组建的军队的最大兵力。

示例

输入 #1

5
3 1 0
1 2 3
3 5 10
2 5 3
4 3 3
3 2 1 2
4 1 0
4 1 4 2
4 1 10
4 1 4 2

输出 #1

4
40
9
13
0

注意

在第一个测试用例中,中土世界的居民可以组建 $$$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$$$。