Reduction Game
Tag(s):

Algorithms, Depth First Search, Graph, Medium

Problem
Editorial
Analytics

You are given an array $A$ consisting of $N$ distinct integers. If the size of the array is greater than one, then you can perform the following operations any number of times:

• Select two integers $A_i$ and $A_j$ such that $CountOnes(A_i \oplus A_j) = 1$ and delete either $A_i$ or $A_j$ from the array. This operation costs $C_1$.

• Select two integers $A_i$ and $A_j$ such that $CountOnes(A_i \oplus A_j) \gt 1$ and delete either $A_i$ or $A_j$ from the array. This operation costs $C_2$.

Here, $CountOnes(X)$ returns the number of $1s$ available in the binary representation of integer $X$. Determine the minimum cost to reduce the size of the array to $1$.

Input format

• First line: $T$ denoting the number of test cases
• For each test case:
• First line: $N$
• Second line: Two space-separated integers $C_1$ and $C_2$
• Third line: $N$ space-separated integers denoting the array $A$

Output format

For each test case, print a single integer in a separate line as described in the problem statement

Constraints

$1 \le T \le 20$

$1\le N\le 10^4$

$1 \le C_1,C_2,A_i \le 10^9$

• For 10 points: $1 \le N \le 10$
• For 90 points: Implement the original constraints
SAMPLE INPUT
1
4
50 100
1 2 3 4
SAMPLE OUTPUT
200

Explanation

We take 1 and 3 and delete 1 with cost 50. Next we take 3 and 2 and delete 2 with cost 50. Last, we take 3 and 4 and delete 4 with cost 100.

So total cost = 50+50+100 = 200

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor 