← 返回题目列表

Codeforces · 850/B

B. Arpa 和数字列表

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

Arpa 找到了一个包含 n 个数字的列表。当且仅当列表不为空且列表中数字的 gcd(更多信息,请参阅注释部分)为 1 时,他才称列表为坏列表。

Arpa 可以执行两种类型的操作:

- 选择一个数字并以成本 x 删除它。
- 选择一个数字并将其加 1,成本为 y。

Arpa 可以将这些操作应用到任意数量的号码上,并且他可以对同一个号码任意多次应用第二个操作。

帮助 Arpa 找到使列表良好的最低可能成本。

输入

第一行包含三个整数 n、x 和 y (1 ≤ n ≤ 5·105, 1 ≤ x, y ≤ 109) - 列表中元素的数量以及整数 x 和 y。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 106) - 列表的元素。

输出

打印单个整数:使列表良好的最小可能成本。

示例

输入 #1

4 23 17
1 17 17 16

输出 #1

40

输入 #2

10 6 2
100 49 71 73 66 96 8 60 41 63

输出 #2

10

注意

例如,数字 1 必须删除(成本为 23),数字 16 必须加 1(成本为 17)。

一组数字的 gcd(最大公约数)是整除该组中所有整数的最大整数。在这里阅读有关 gcd 的更多信息。