← 返回题目列表

Codeforces · 2194/B

B. 离岸

中文机器翻译题面 查看原题

马克非常爱钱,他把大部分钱存在银行里。他将钱存放在不同的银行中。在第 $$$i$$$ 银行,他有 $$$a_i$$$ 卢布。

有一天,马克决定将所有钱集中到一家银行,因此他将把钱从一个银行账户转移到另一个银行账户。所有银行间转账的安排都是一样的:他一次只能转账 $$$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$$$。

输出

对于每个测试用例,输出一个数字——任何银行可以获得的最大卢布数量。

示例

输入
复制

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

输出
复制

25
229
2000
113
72
74

注意

在第一个测试用例中,最佳传输顺序可能如下所示:$$1\to4,\; 1\到4,\; 4\到3,\; 4\到3,\; 4\到3,\; 3\到2,\; 3\到2,\; 3\到2,\; 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$$$ 卢布。