Arpa has found a list containing _n_ numbers. He calls a list bad if and only if it is not empty and _gcd_ (see notes section for more information) of numbers in the list is 1.
Arpa can perform two types of operations:
* Choose a number and delete it with cost _x_.
* Choose a number and increase it by 1 with cost _y_.
Arpa can apply these operations to as many numbers as he wishes, and he is allowed to apply the second operation arbitrarily many times on the same number.
Help Arpa to find the minimum possible cost to make the list good.
## Input
First line contains three integers _n_, _x_ and _y_ (1 ≤ _n_ ≤ 5·105, 1 ≤ _x_, _y_ ≤ 109) — the number of elements in the list and the integers _x_ and _y_.
Second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the elements of the list.
## Output
Print a single integer: the minimum possible cost to make the list good.
[samples]
## Note
In example, number 1 must be deleted (with cost 23) and number 16 must increased by 1 (with cost 17).
A _gcd_ (greatest common divisor) of a set of numbers is the maximum integer that divides all integers in the set. Read more about gcd [here](https://en.wikipedia.org/wiki/Greatest_common_divisor).
Arpa 找到了一个包含 #cf_span[n] 个数字的列表。他称一个列表为“坏的”，当且仅当它非空且列表中数字的 _gcd_（详见注释部分）为 #cf_span[1]。
Arpa 可以执行两种操作：
Arpa 可以对任意多个数字应用这些操作，并且允许对同一个数字无限次应用第二种操作。
帮助 Arpa 找到使列表变为“好的”所需的最小代价。
第一行包含三个整数 #cf_span[n], #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ n ≤ 5·105], #cf_span[1 ≤ x, y ≤ 109]）— 列表中元素的个数以及整数 #cf_span[x] 和 #cf_span[y]。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 106]）— 列表的元素。
请输出一个整数：使列表变为“好的”所需的最小可能代价。
在示例中，数字 #cf_span[1] 必须被删除（代价为 #cf_span[23]），数字 #cf_span[16] 必须增加 #cf_span[1]（代价为 #cf_span[17]）。
一组数字的 _gcd_（最大公约数）是能整除集合中所有整数的最大整数。更多关于 gcd 的信息请参见此处。
## Input
第一行包含三个整数 #cf_span[n], #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ n ≤ 5·105], #cf_span[1 ≤ x, y ≤ 109]）— 列表中元素的个数以及整数 #cf_span[x] 和 #cf_span[y]。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 106]）— 列表的元素。
## Output
请输出一个整数：使列表变为“好的”所需的最小可能代价。
[samples]
## Note
在示例中，数字 #cf_span[1] 必须被删除（代价为 #cf_span[23]），数字 #cf_span[16] 必须增加 #cf_span[1]（代价为 #cf_span[17]）。一组数字的 _gcd_（最大公约数）是能整除集合中所有整数的最大整数。更多关于 gcd 的信息请参见此处。
Let $ n, x, y \in \mathbb{N} $, with $ 1 \leq n \leq 5 \cdot 10^5 $, $ 1 \leq x, y \leq 10^9 $.
Let $ A = [a_1, a_2, \dots, a_n] $ be a sequence of integers with $ 1 \leq a_i \leq 10^6 $.
Define a list as **bad** if $ \gcd(A) = 1 $ and $ A \neq \emptyset $.
Define a list as **good** if it is either empty or $ \gcd(A) > 1 $.
Two operations are allowed:
1. **Delete** any element $ a_i $ at cost $ x $.
2. **Increment** any element $ a_i $ by 1, any number of times, at cost $ y $ per increment.
Let $ c_i(k) $ denote the cost to transform $ a_i $ into $ a_i + k $ via increment operations: $ c_i(k) = k \cdot y $, for $ k \geq 0 $.
Let $ S \subseteq \{1, 2, \dots, n\} $ be the set of indices of elements **retained**.
Let $ B = \{ a_i + k_i \mid i \in S, k_i \in \mathbb{N}_0 \} $ be the multiset of resulting values.
The goal is to choose $ S $ and non-negative integers $ \{k_i\}_{i \in S} $ such that:
- $ \gcd(B) > 1 $,
- Total cost $ = (n - |S|) \cdot x + \sum_{i \in S} k_i \cdot y $ is minimized.
Find the **minimum total cost** over all such choices of $ S $ and $ \{k_i\} $.
---
**Note:** Since $ \gcd(B) > 1 $, there must exist some prime $ p \geq 2 $ such that $ p \mid b $ for all $ b \in B $.
Thus, the problem reduces to:
For each prime $ p \leq \max(A) + K $ (where $ K $ is the maximum number of increments we might consider),
compute the minimum cost to make all retained elements divisible by $ p $,
then take the minimum over all such $ p $.
For a fixed prime $ p $, for each $ a_i $:
- The minimal number of increments to make $ a_i $ divisible by $ p $ is $ d_i(p) = (p - (a_i \bmod p)) \bmod p $.
- Cost to keep $ a_i $: $ d_i(p) \cdot y $.
- Cost to delete $ a_i $: $ x $.
- So, for each $ a_i $, optimal choice: $ \min(x, d_i(p) \cdot y) $.
Total cost for prime $ p $: $ \sum_{i=1}^n \min(x, d_i(p) \cdot y) $.
We must compute this over all primes $ p $ such that $ p \leq \max(A) + \left\lfloor \frac{x}{y} \right\rfloor $, since increments beyond $ \lfloor x/y \rfloor $ are never better than deletion.
Let $ M = \max(A) $, and let $ P $ be the set of all primes $ \leq M + \left\lfloor \frac{x}{y} \right\rfloor $.
Then, the answer is:
$$
\min_{p \in P} \sum_{i=1}^n \min\left(x, \left( (p - (a_i \bmod p)) \bmod p \right) \cdot y \right)
$$
Additionally, consider the cost of deleting all elements: $ n \cdot x $.
Thus, final answer:
$$
\min\left( n \cdot x,\ \min_{p \in P} \sum_{i=1}^n \min\left(x, \left( (p - (a_i \bmod p)) \bmod p \right) \cdot y \right) \right)
$$