У Василия есть массив из \(n\) чисел \(a_1, a_2, \dots, a_n\). Он может любое количество раз выполнить следующую последовательность операций:
- выбрать два любых элемента массива \(a_i\) и \(a_j\), где \(a_i\) должно делиться нацело на \(2\)
- \(a_i = \frac{a_i}{2}\)
- \(a_j = a_j \cdot 2\)
Помогите Василию найти максимальную сумму элементов массива, которую он сможет добиться, используя описанную последовательность операций.
Выходные данные
Для каждого набора входных данных выведите максимальную сумму элементов массива после оптимального применения последовательности операций.
Примечание
В первом тестовом примере оптимальный порядок выглядит следующим образом:
- Выбрать \(i = 2\) и \(j = 1\). После выполнения последовательности операций \(a_2 = \frac{4}{2} = 2\) и \(a_1 = 6 \cdot 2 = 12\), массив будет следующим: [12, 2, 2].
- Выбрать \(i = 2\) и \(j = 1\). После выполнения последовательности операций \(a_2 = \frac{2}{2} = 1\) и \(a_1 = 12 \cdot 2 = 24\), массив будет следующим: [24, 1, 2].
- Выбрать \(i = 3\) и \(j = 1\). После выполнения последовательности операций \(a_3 = \frac{2}{2} = 1\) и \(a_1 = 24 \cdot 2 = 48\), массив будет следующим: [48, 1, 1].
Итоговый ответ \(48 + 1 + 1 = 50\).
В третьем тестовом примере нет возможности поменять сумму элементов, поэтому ответ \(10\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
6 4 2
5
1 2 3 4 5
1
10
3
2 3 4
15
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
|
50
46
10
26
35184372088846
|