Даны два массива \(a\) и \(b\) длины \(n\).
Вы можете любое количество раз (возможно, ноль) выполнить следующую операцию: выбрать индекс \(i\) (\(1 \leq i \leq n\)) и поменять местами \(a_i\) и \(b_i\).
Назовем стоимостью массива \(a\) величину, равную \(\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2\). Аналогично, стоимость массива \(b\) будет равна \(\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (b_i + b_j)^2\).
Вам необходимо минимизировать суммарную стоимость двух массивов.
Выходные данные
Для каждого набора входных данных выведите минимальную возможную суммарную стоимость двух массивов.
Примечание
Во втором наборе входных данных в одном из оптимальных ответов после выполнения операций \(a = [2, 6, 4, 6]\), \(b = [3, 7, 6, 1]\).
Стоимость массива \(a\) равна \((2 + 6)^2 + (2 + 4)^2 + (2 + 6)^2 + (6 + 4)^2 + (6 + 6)^2 + (4 + 6)^2 = 508\).
Стоимость массива \(b\) равна \((3 + 7)^2 + (3 + 6)^2 + (3 + 1)^2 + (7 + 6)^2 + (7 + 1)^2 + (6 + 1)^2 = 479\).
Суммарная стоимость массивов равна \(508 + 479 = 987\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
3
6
4
3 6 6 6
2 7 4 1
4
6 7 2 4
2 5 3 5
|
0
987
914
|