CF1609A Divide and Multiply

William 有一个包含 $n$ 个数的数组 $a_1, a_2, \dots, a_n$。他可以任意次数地执行以下操作序列： 1. 从数组中任选两个元素 $a_i$ 和 $a_j$，其中 $a_i$ 必须是 $2$ 的倍数； 2. 令 $a_i = \frac{a_i}{2}$； 3. 令 $a_j = a_j \cdot 2$。 请你帮助 William 求出通过上述操作序列后，数组元素和的最大值。

每组测试数据包含多组测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 15$），表示 William 的数组中元素的个数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i < 16$），表示 William 的数组内容。

对于每组测试用例，输出通过最优操作序列后数组元素和的最大值。

在第一个样例测试用例中，最优的操作序列如下： 1. 选择 $i = 2$ 和 $j = 1$。操作后 $a_2 = \frac{4}{2} = 2$，$a_1 = 6 \cdot 2 = 12$，数组变为 $[12, 2, 2]$。 2. 选择 $i = 2$ 和 $j = 1$。操作后 $a_2 = \frac{2}{2} = 1$，$a_1 = 12 \cdot 2 = 24$，数组变为 $[24, 1, 2]$。 3. 选择 $i = 3$ 和 $j = 1$。操作后 $a_3 = \frac{2}{2} = 1$，$a_1 = 24 \cdot 2 = 48$，数组变为 $[48, 1, 1]$。 最终答案为 $48 + 1 + 1 = 50$。 在第三个样例测试用例中，没有办法改变元素和，因此答案为 $10$。 由 ChatGPT 4.1 翻译