Description

Qingzhengyu is an unbeaten player in the game “Chilan Xianye”. One day, he encountered the following game:

You are given an array $a$ of length $n$. Also define $count(x)$ as the number of $1$ bits in the binary representation of $x$.

Each time, Qingzhengyu can perform one of the following two operations:

• Choose two numbers $a_i, a_j$, and it must satisfy $count(a_i \operatorname{xor} a_j)=1$. Delete either one of them from the array, with cost $C_1$.

• Choose two numbers $a_i, a_j$, and it must satisfy $count(a_i \operatorname{xor} a_j) > 1$. Delete either one of them from the array, with cost $C_2$.

You want to know the minimum total cost to delete numbers until only one number remains in the array.

Input Format

The first line contains an integer $n$, which is the size of the array.
The second line contains two integers $C_1, C_2$, with meanings as described above.
The third line contains $n$ integers, describing the array $a$.

Output Format

Output one integer in one line, representing the minimum cost.

4
5 10
1 2 3 4

20

Hint

For $20\%$ of the testdata, $n = 10$.
For another $20\%$ of the testdata, the elements in $a$ form a permutation of $[1, n]$.
For $100\%$ of the testdata, $1 \leq n \leq {10}^4$, $1 \le C_1, C_2, a \le {10}^9$, and all elements in $a$ are distinct.

Translated by ChatGPT 5