Problem Description

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$.)

Input Format

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.

Output Format

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

6
4 1 2
4 5 6 7
5 2 8
0 -1 -2 -6 7
6 -1 -2
1 2 3 4 5 6
6 3 4
-1 0 0 1 2 3
6 -3 -4
1 0 0 -1 -2 -3
5 1 -10
-9 2 -5 3 -7

35
56
0
23
23
165

Hint

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