У Василия есть массив из \(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)\) — описание массива Василия.
Для каждого набора входных данных выведите максимальную сумму элементов массива после оптимального применения последовательности операций.
В первом тестовом примере оптимальный порядок выглядит следующим образом:
Итоговый ответ \(48 + 1 + 1 = 50\).
В третьем тестовом примере нет возможности поменять сумму элементов, поэтому ответ \(10\).
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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач