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 的更多信息。