← 返回题目列表

AtCoder · arc144_b

B. 赠与税

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

分数: 400 点

问题陈述

给你正整数 a 和 b 这样 a\leq b,以及正整数序列 A = (A_1, A_2, \ldots, A_N).

在此序列中,您可以执行以下操作任意次数(可能为零):

  • 选择不同的索引 i, j (1\leq i, j \leq N)。添加 a to A_i 并减去 b 来自 A_j.

找到最大可能值 \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