You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

马克是一位星际旅行者，他在 $n$ 个不同的星际银行中存有货币。在第 $i$ 个银行中，他存有 $a_i$ 个单位的信用点。

为了方便管理，马克决定将所有资金尽可能地汇集到某一个银行账户中。然而，星际银行之间的转账遵循严格的协议：

1. 固定转账额度：每次转账必须恰好转出 $x$ 个信用点。
2. 汇率损耗：由于跨行转账存在手续费，当你从一个银行转出 $x$ 个信用点时，目标银行账户只会收到 $y$ 个信用点（保证 $y \leq x$）。

马克可以进行任意次数的转账。他的目标是：通过合理的转账策略，使得最终某一个银行中的信用点数量尽可能多。

请计算出在所有可能的策略中，某个银行能达到的最大信用点余额。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。 每个测试用例包含两行：

第一行包含三个整数 $n, x, y$ ($2 \le n \le 2 \cdot 10^5, 1 \le y \le x \le 10^9$)。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$)，表示各银行初始余额。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

每个测试用例输出一个整数，表示某个银行账户能达到的最大金额。

输入输出样例 #1

输入 #1

6
4 5 4
10 9 8 7
5 13 11
47 52 64 13 91
2 1 1
1000 1000
3 15 14
34 43 52
6 7 6
15 17 14 15 12 16
2 15 10
45 44

输出 #1

25
229
2000
113
72
74

说明/提示

在第一个测试用例中，最佳转移序列可能如下所示：

$1\to4 , 1\to4 , 4\to3 , 4\to3 , 4\to3 , 3\to2 , 3\to2 , 3\to2 , 3\to2.$

让我们展示每一步后的和的变化： $(10,9,8,7) \xrightarrow{1\to4} (5,9,8,11) \xrightarrow{1\to4} (0,9,8,15) \xrightarrow{4\to3} (0,9,12,10) \xrightarrow{4\to3} (0,9,16,5) \xrightarrow{4\to3} (0,9,20,0) \xrightarrow{3\to2} (0,13,15,0) \xrightarrow{3\to2} (0,17,10,0) \xrightarrow{3\to2} (0,21,5,0) \xrightarrow{3\to2} (0,25,0,0).$

因此，在一家银行（具体是第二家），可以获得 $25$ 卢布，而这个值是该测试用例的答案。

在第三个测试用例中，可以将一卢布从第一家银行转移到第二家银行 $1000$ 次，并在第二家银行获得 $2000$ 卢布。