P16212 [ECUSTPC 2025] Autumn Fortress.

Maddy has arrived in front of the fortress in autumn. She collected $n$ ingredients, whose freshness values are $a_1, a_2, \dots, a_n$. Maddy will use these ingredients to cook dinners for several days. In particular, since she only has two recipes with skill values $x$ and $y$, she will cook exactly two dishes every day, not one less. The cooking process for each day is as follows: - Maddy may pick two different ingredients that have not been picked before, in any order. Let their freshness values be $a$ and $b$. Then she cooks them, assigning one recipe to each ingredient. The deliciousness values of the two dishes are $ax$ and $by$, so the total deliciousness of that day's dinner is $ax + by$. Note that Maddy may assign the two ingredients to the two recipes in any order, and each day's dinner must use 2 different ingredients to make 2 dishes. Please help Maddy choose how many days to cook dinner, and compute the maximum possible total deliciousness $D$ over those days. (Of course, if everything tastes terrible, she can also choose not to cook at all, i.e., the number of days can be $0$.)

The first line contains an integer $T$ ($1 \le T \le 10^5$), the number of test cases. For each test case, the first line contains three integers $n, x, y$ ($2 \le n \le 10^5, -10^6 \le x, y \le 10^6$), representing the number of ingredients and the skill values of the two recipes. The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^6 \le a_i \le 10^6$), representing the freshness of each ingredient. It is guaranteed that $\sum n \le 3 \times 10^5$ over all test cases.

For each test case, output one integer $D$ in one line, representing the maximum possible total deliciousness over those days.

### Explanation for Sample 1 For the 1st sample, we consider cooking dinner for 2 days: - On day 1, choose ingredients with freshness $7$ and $5$, and assign them to the recipes with skill values $2$ and $1$, respectively. The dinner has deliciousness $7 \times 2 + 5 \times 1 = 19$; - On day 2, choose ingredients with freshness $6$ and $4$, and assign them to the recipes with skill values $2$ and $1$, respectively. The dinner has deliciousness $6 \times 2 + 4 \times 1 = 16$. The total deliciousness is $35$. For the 2nd sample, we consider cooking dinner for 1 day: choose ingredients with freshness $7$ and $0$, and assign them to the recipes with skill values $8$ and $2$, respectively. The dinner has deliciousness $7 \times 8 + 0 \times 2 = 56$. For the 3rd sample, we consider not cooking dinner, because in any case the deliciousness of the dinner is negative. Translated by ChatGPT 5