У Василия есть массив из $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$. Он может любое количество раз выполнить следующую последовательность операций:
Помогите Василию найти максимальную сумму элементов массива, которую он сможет добиться, используя описанную последовательность операций.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ $$$(1 \le n \le 15)$$$ — количество элементов в массиве Василия.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i < 16)$$$ — описание массива Василия.
Для каждого набора входных данных выведите максимальную сумму элементов массива после оптимального применения последовательности операций.
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
В первом тестовом примере оптимальный порядок выглядит следующим образом:
Итоговый ответ $$$48 + 1 + 1 = 50$$$.
В третьем тестовом примере нет возможности поменять сумму элементов, поэтому ответ $$$10$$$.
Название |
---|