题目描述

Maddy 来到了秋天的堡垒之前，在此她采集了 $n$ 个食材，这些食材的新鲜度分别为 $a_1, a_2, \dots, a_n$。

Maddy 会用这些食材做若干天的晚饭。特别地，因为她只有两个技艺值分别为 $x, y$ 的食谱，她每天会做且只会做两道菜，少一道都不行。

每一天做饭的流程如下：

• Maddy 可以以任意顺序选取两个不同且未被选择过的食材，记其新鲜度分别为 $a, b$；
• 随后对其进行烹饪，每个食材对应一个食谱，所制作出的菜肴的美味值分别为 $a \times x$ 和 $b \times y$。
• 当天晚饭总的美味值即为 $a \times x + b \times y$。

注意，Maddy 可以以任意顺序选择食材对应的食谱，且每天晚饭必须选择 $2$ 个不同的食材制作 $2$ 道菜肴。

请帮助 Maddy 选取做晚饭的天数，并求出在最优的情况下，这几天晚饭的总美味值 $D$。（当然如果做出来的菜都太难吃了，也可以不做，换言之天数可以取 $0$。）

输入格式

第一行包含一个整数 $T$ —— 表示测试数据的组数。

对于每组测试数据：

• 第一行包含三个整数 $n, x, y$ —— 分别表示食材的个数以及两个食谱的技艺值。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 表示各个食材的新鲜度。

输出格式

对于每组测试数据，输出一行一个整数 $D$，表示在最优的情况下，这几天晚饭的总美味值。

样例输入 1

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

样例输出 1

35
56
0
23
23
165

说明

样例解释

• 对于第 $1$ 个样例，我们考虑做 $2$ 天的晚饭，其中：
  • 第一天选用新鲜度分别为 $7$ 和 $5$ 的食材分别对应技艺值为 $2, 1$ 的食谱，可以烹饪出美味值为 $7 \times 2 + 5 \times 1 = 19$ 的晚饭；
  • 第二天选用新鲜度分别为 $6$ 和 $4$ 的食材分别对应技艺值为 $2, 1$ 的食谱，可以烹饪出美味值为 $6 \times 2 + 4 \times 1 = 16$ 的晚饭。 总的美味值为 $35$。
• 对于第 $2$ 个样例，我们考虑做 $1$ 天的晚饭，选用新鲜度分别为 $7$ 和 $0$ 的食材分别对应技艺值为 $8, 2$ 的食谱，可以烹饪出美味值为 $7 \times 8 + 0 \times 2 = 56$ 的晚饭。
• 对于第 $3$ 个样例，我们考虑不做晚饭，因为任何情况下做出的晚饭的美味值均是负的，此时输出 $0$。

数据范围

• 对于所有测试点，保证 $1 \le T \le 10^5$。
• 对于每组测试数据，保证 $2 \le n \le 10^5$。
• 对于每组测试数据，保证 $-10^6 \le x, y \le 10^6$。
• 对于每组测试数据，保证 $-10^6 \le a_i \le 10^6$。
• 保证同一测试点内所有测试数据的 $n$ 之和满足 $\sum n \le 3 \times 10^5$。
• 保证所有的输入数值均为整数。