Тропический минимум. Задача

Миша получил загадочную посылку из далёкой страны. Открыв её, он обнаружил внутри тропический калькулятор, а также массив целых чисел. При ближайшем рассмотрении
Миша понял, что калькулятор умеет вычислять результат довольно длинных выражений с
операциями сложения и умножения, однако не умеет обрабатывать скобки. При ещё более детальном рассмотрении он обнаружил, что в качестве результата сложения двух чисел
калькулятор возвращает минимальное из чисел вместо их суммы, а в качестве результата
умножения — сумму множителей вместо произведения. Мише сразу же стало интересно, какое минимальное число может получиться, если он расставит между числами в присланном
ему массиве операции сложения и умножения, после чего вычислит на калькуляторе результат полученного выражения. Обратите внимание, что числа в массиве переставлять нельзя,
а приоритет умножения у калькулятора выше, чем у сложения, несмотря на то, что сами
операции необычны.
Формат входных данных
В первой строке задано одно число T — количество наборов входных данных, для которых
нужно решить задачу. В
следующей строке заданы через пробел n целых чисел a1, a2, . . . , an — элементы массива.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 10^6
.
Пример.
Стандартный ввод.
4
7
-1 -1 -1 2 -1 -1 -1
3
7 3 6
5
10 -50 20 -100 30
3
-100 100 100.
Стандартный вывод.
-4
3
-130
-100

0