Minimum Cost to Reduce Array

You are given an array of n integers: \(a_1, a_2, \ldots, a_n\). Additionally, define \(\text{count}(x)\) to be the number of 1's in the binary representation of \(x\). You can perform the following two types of operations any number of times:

• Choose two elements \(a_i\) and \(a_j\) such that \(\text{count}(a_i \oplus a_j) = 1\), then remove one of them from the array at a cost of \(C_1\).
• Choose two elements \(a_i\) and \(a_j\) such that \(\text{count}(a_i \oplus a_j) > 1\), then remove one of them from the array at a cost of \(C_2\).

Your goal is to reduce the array until only one element remains. Compute the minimum total cost to achieve this. If it is impossible to reduce the array to one element using the rules above, output -1.

Observation: Notice that each removal operation can be seen as selecting an edge between two distinct elements (since if \(a_i = a_j\), then \(a_i \oplus a_j = 0\) and no operation is allowed). The cost of an edge between two distinct elements is \(C_1\) if \(\text{count}(a_i \oplus a_j) = 1\) and \(C_2\) if \(\text{count}(a_i \oplus a_j) > 1\). Thus, the problem is equivalent to choosing \(n-1\) operations (edges) that connect all elements, i.e. forming a spanning tree with minimum total cost.

inputFormat

The first line contains three integers: n (the number of elements), C_1, and C_2.

The second line contains n space-separated integers \(a_1, a_2, \ldots, a_n\).

outputFormat

Output a single integer which is the minimum total cost to reduce the array to one element. If it is impossible, output -1.

sample

1 10 20
5

0