Приближается лунный новый год, а Боб все еще мучается со своей домашней работой — задачей о разделении чисел.
Даны \(n\) положительных целых чисел \(a_1, a_2, \ldots, a_n\), где \(n\) всегда четно. Боб должен разделить эти числа на группы, причем каждая группа должна содержать хотя бы \(2\) числа. Предположим, что числа разделены на \(m\) групп, и сумма чисел в \(j\)-й группе равна \(s_j\). Цель Боба — минимизировать сумму квадратов \(s_j\), то есть \(\)\sum_{j = 1}^{m} s_j^2.\(\)
Боб никак не может решить эту задачу. Можете ему помочь?
Выходные данные
Выведите одно целое число, равное минимальной возможной сумме \(s_j\), то есть \(\)\sum_{i = j}^{m} s_j^2,\(\) где \(m\) — число групп чисел.
Примечание
В первом примере одно из оптимальных решений — разделить эти \(4\) числа на \(2\) две группы: \(\{2, 8\}, \{5, 3\}\). Ответ равен \((2 + 8)^2 + (5 + 3)^2 = 164\).
Во втором примере одно из оптимальных решений — разделить эти \(6\) чисел на \(3\) группы: \(\{1, 2\}, \{1, 2\}, \{1, 2\}\). Ответ равен \((1 + 2)^2 + (1 + 2)^2 + (1 + 2)^2 = 27\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
8 5 2 3
|
164
|
|
2
|
6
1 1 1 2 2 2
|
27
|