题目描述

给定满足 $a \leq b$ 的正整数 $a$、$b$，以及一个正整数序列 $A = (A_1, A_2, \ldots, A_N)$。

你可以对该数列进行如下操作任意次（也可以一次都不做）：

• 选择两个不同的下标 $i, j$（$1 \leq i, j \leq N$），将 $A_i$ 加上 $a$，并将 $A_j$ 减去 $b$。

请你求出操作后 $\min(A_1, A_2, \ldots, A_N)$ 可能取得的最大值。

输入格式

输入以如下格式从标准输入读入：

$N$ $a$ $b$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出操作后 $\min(A_1, A_2, \ldots, A_N)$ 可能取得的最大值。

样例 1

输入

3 2 2
1 5 9

输出

5

样例 2

输入

3 2 3
11 1 2

输出

3

样例 3

输入

3 1 100
8 5 6

输出

5

样例 4

输入

6 123 321
10 100 1000 10000 100000 1000000

输出

90688

说明/提示

限制条件

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq a \leq b \leq 10^9$
• $1 \leq A_i \leq 10^{9}$

样例解释 1

例如，可以通过如下操作使 $\min(A_1, A_2, A_3) = 5$：

• 以 $i = 1, j = 3$ 进行操作。$A$ 变为 $(3, 5, 7)$。
• 再以 $i = 1, j = 3$ 进行操作。$A$ 变为 $(5, 5, 5)$。

样例解释 2

例如，可以通过如下操作使 $\min(A_1, A_2, A_3) = 3$：

• 以 $i = 1, j = 3$ 进行操作。$A$ 变为 $(13, 1, -1)$。
• 以 $i = 2, j = 1$ 进行操作。$A$ 变为 $(10, 3, -1)$。
• 以 $i = 3, j = 1$ 进行操作。$A$ 变为 $(7, 3, 1)$。
• 以 $i = 3, j = 1$ 进行操作。$A$ 变为 $(4, 3, 3)$。

样例解释 3

如果一次操作都不进行，可以使 $\min(A_1, A_2, A_3) = 5$。

由 ChatGPT 4.1 翻译