Lonely Mountain Dungeons
Contest: Codeforces Round 924 (Div. 2)
Difficulty rating: 1900
Tags: brute force, data structures, greedy, math, ternary search

Once, the people, elves, dwarves, and other inhabitants of Middle-earth gathered to reclaim the treasures stolen from them by Smaug. In the name of this great goal, they rallied around the powerful elf Timothy and began to plan the overthrow of the ruler of the Lonely Mountain.

The army of Middle-earth inhabitants will consist of several squads. It is known that each pair of creatures of the same race, which are in different squads, adds $$$b$$$ units to the total strength of the army. But since it will be difficult for Timothy to lead an army consisting of a large number of squads, the total strength of an army consisting of $$$k$$$ squads is reduced by $$$(k - 1) \cdot x$$$ units. Note that the army always consists of at least one squad.

It is known that there are $$$n$$$ races in Middle-earth, and the number of creatures of the $$$i$$$-th race is equal to $$$c_i$$$. Help the inhabitants of Middle-earth determine the maximum strength of the army they can assemble.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$b$$$, and $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le b \le 10^6, 0 \le x \le 10^9$$$) — the number of races and the constants $$$b$$$ and $$$x$$$ described above.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 2 \cdot 10^5$$$) — the number of creatures of each of the $$$n$$$ races.

It is guaranteed that the sum of the values $$$c_1 + c_2 + \ldots + c_n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the maximum strength of the army that the inhabitants of Middle-earth can assemble.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the inhabitants of Middle-earth can form $$$3$$$ squads. Since $$$x = 0$$$, the army's strength will not decrease due to the number of squads. The inhabitants can be distributed among the squads as follows:

- The single representative of the first species can be sent to the first squad.
- The first representative of the second species can be sent to the first squad, the second representative of the second species can be sent to the second squad. Then the total strength of the army will increase by $$$b = 1$$$.
- The first representative of the third species can be sent to the first squad, the second representative of the third species can be sent to the second squad, the third representative of the third species can be sent to the third squad. Then the total strength of the army will increase by $$$3 \cdot b = 3$$$, as they form three pairs in different squads.

Thus, the total strength of the army is $$$4$$$.

In the second test case, the inhabitants of Middle-earth can form $$$3$$$ squads. Since $$$x = 10$$$, the army's strength will decrease by $$$20$$$. The inhabitants can be distributed among the squads as follows:

- The first representative of the first species can be sent to the first squad, the second representative of the first species can be sent to the second squad. Then the total strength of the army will increase by $$$b = 5$$$.
- The first and second representatives of the second species can be sent to the first squad, the third and fourth representatives of the second species can be sent to the second squad, the fifth representative of the second species can be sent to the third squad. Then the total strength of the army will increase by $$$8 \cdot b = 40$$$.
- The first representative of the third species can be sent to the first squad, the second representative of the third species can be sent to the second squad, the third representative of the third species can be sent to the third squad. Then the total strength of the army will increase by $$$3 \cdot b = 15$$$, as they form three pairs in different squads.

Thus, the total strength of the army is $$$5 + 40 + 15 - 20 = 40$$$.

Example input:
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

Example output:
4
40
9
13
0

Editorial:
Let's learn how to solve the problem when $$$n = 1$$$. Suppose there is only one race and the number of its representatives is $$$c$$$. Notice that for a fixed $$$k$$$, it is advantageous for us to divide the representatives of the race almost evenly into squads.
If $$$c$$$ is divisible by $$$k$$$, then it is advantageous for us to take exactly $$$y = \frac{c}{k}$$$ beings in each squad. Then the total number of pairs of beings in different squads is equal to $$$\frac{k(k-1)}{2} \cdot y^2$$$ (there are a total of $$$\frac{k(k-1)}{2}$$$ pairs of squads, and for each pair of squads there are $$$y^2$$$ pairs of beings from different squads).
In the general case, when $$$c$$$ may not be divisible by $$$k$$$, let's denote $$$y = \left\lfloor \frac{c}{k} \right\rfloor$$$ and $$$y' = \left\lceil \frac{c}{k} \right\rceil$$$. Then it is advantageous for us to make squads of size $$$y$$$ and $$$y'$$$, where the number of squads of size $$$y'$$$ is equal to $$$c \bmod k$$$ (we essentially make all squads of size $$$y$$$, and then add 1 to some squads from the remaining part). In this case, the total number of pairs of beings in different squads is equal to $$$C_{k - c \bmod k}^2 \cdot y^2 + C_{c \bmod k}^2 \cdot y'^2 + (k - c \bmod k) \cdot (c \bmod k) \cdot y \cdot y'$$$. It remains to notice that it makes no sense to have $$$k > c$$$, so we can simply iterate through $$$k$$$ from $$$1$$$ to $$$c$$$ and choose the optimal one.
When $$$n > 1$$$, we can notice that for a fixed $$$k$$$, we can solve the problem independently for each race. Let the number of representatives of the $$$i$$$-th race be $$$c_i$$$. Then we will iterate through $$$k$$$ from $$$1$$$ to $$$c_i$$$ for it and add the maximum total strength to the value of $$$cnt_k$$$ (the array $$$cnt$$$ is common for all races). Also, notice that for $$$k > c_i$$$, we will get the same total strength as for $$$k = c_i$$$. Then in the additional array $$$add$$$ (again, common for all races), we will add the maximum total strength for $$$k = c_i$$$ to $$$add_{c_i}$$$.
We get the following solution: first, calculate the described arrays $$$cnt$$$ and $$$add$$$. After that, iterate through $$$k$$$ from $$$1$$$ to the maximum $$$c_i$$$. The maximum total strength of the squads for a fixed $$$k$$$ will be equal to $$$(cnt_k + (\text{sum of values } add_i \text{ for } i < k)) \cdot b - (k - 1) \cdot X$$$. From these values, we need to choose the maximum.