Вам дано \(n\) целых чисел \(a_1, a_2, \ldots, a_n\). Для любого вещественного числа \(t\) рассмотрим полный взвешенный граф на \(n\) вершинах \(K_n(t)\) с весом ребра между вершинами \(i\) и \(j\), равным \(w_{ij}(t) = a_i \cdot a_j + t \cdot (a_i + a_j)\).
Пусть \(f(t)\) будет стоимостью минимального остовного дерева для \(K_n(t)\). Определите, ограничена ли \(f(t)\) сверху, и если да, то выведите максимальное значение, которое она достигает.
Выходные данные
Для каждого набора входных данных выведите одну строку с максимальным значением \(f(t)\) (можно показать, что это целое число) или «INF», если \(f(t)\) не ограничена сверху.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
1 0
2
-1 1
3
1 -1 -2
3
3 -1 -2
4
1 2 3 -4
|
INF
-1
INF
-6
-18
|