/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
a\leq b を満たす正整数 a, b および，正整数列 A = (A_1, A_2, \ldots, A_N) が与えられます．
あなたはこの数列に対して，以下の操作を何度でも行うことができます（0 回でもよいです）：
- 相異なる添字 i, j (1\leq i, j \leq N) を選ぶ．A_i に a を加え，A_j から b を引く．
操作後の \min(A_1, A_2, \ldots, A_N) としてありうる最大値を求めてください．
制約
- 2\leq N\leq 3\times 10^5
- 1\leq a\leq b\leq 10^9
- 1\leq A_i\leq 10^{9}
入力
入力は以下の形式で標準入力から与えられます．
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
出力例 1
5
例えば次のように操作を行うことで， \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
3 2 3 11 1 2
出力例 2
3
例えば次のように操作を行うことで， \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
3 1 100 8 5 6
出力例 3
5
一度も操作を行わないことにより， \min(A_1, A_2, A_3) = 5 を達成できます．
入力例 4
6 123 321 10 100 1000 10000 100000 1000000
出力例 4
90688
Score : 400 points
Problem Statement
You are given positive integers a and b such that a\leq b, and a sequence of positive integers A = (A_1, A_2, \ldots, A_N).
On this sequence, you can perform the following operation any number of times (possibly zero):
- Choose distinct indices i, j (1\leq i, j \leq N). Add a to A_i and subtract b from A_j.
Find the maximum possible value of \min(A_1, A_2, \ldots, A_N) after your operations.
Constraints
- 2\leq N\leq 3\times 10^5
- 1\leq a\leq b\leq 10^9
- 1\leq A_i\leq 10^{9}
Input
Input is given from Standard Input in the following format:
N a b A_1 A_2 \ldots A_N
Output
Print the maximum possible value of \min(A_1, A_2, \ldots, A_N) after your operations.
Sample Input 1
3 2 2 1 5 9
Sample Output 1
5
Here is one way to achieve \min(A_1, A_2, A_3) = 5.
- Perform the operation with i = 1, j = 3. A becomes (3, 5, 7).
- Perform the operation with i = 1, j = 3. A becomes (5, 5, 5).
Sample Input 2
3 2 3 11 1 2
Sample Output 2
3
Here is one way to achieve \min(A_1, A_2, A_3) = 3.
- Perform the operation with i = 1, j = 3. A becomes (13, 1, -1).
- Perform the operation with i = 2, j = 1. A becomes (10, 3, -1).
- Perform the operation with i = 3, j = 1. A becomes (7, 3, 1).
- Perform the operation with i = 3, j = 1. A becomes (4, 3, 3).
Sample Input 3
3 1 100 8 5 6
Sample Output 3
5
You can achieve \min(A_1, A_2, A_3) = 5 by not performing the operation at all.
Sample Input 4
6 123 321 10 100 1000 10000 100000 1000000
Sample Output 4
90688