B - Gift Tax Editorial /

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_ia を加え,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