Ikony na pasku

Limit pamięci: 64MB

Marek pracuje nad swoim edytorem grafiki, który posiada wiele interesujących funkcji. Dla każdej funkcji edytora stworzył on ikonę, będącą kwadratowym obrazkiem. Ikony te mają być rozmieszczone na pasku złożonym z dwóch wierszy i N kolumn.

Wysokość wiersza paska jest taka sama jak rozmiar największej ikony w wierszu. Podobnie, szerokość kolumny jest taka sama jak rozmiar największej ikony w kolumnie. Wysokość paska to suma wysokości wszystkich wierszy. Szerokość paska to suma szerokości wszystkich kolumn.
Marek zastanawia się, jak powinien rozmieścić ikony, żeby pole paska było najmniejsze możliwe.

1009998
312
Wysokość tego paska to 100+3, a szerokość to 100+99+98. A zatem pole paska to (100+3)*(100+99+98)=30,591.}

Dany jest posortowany ciąg liczb całkowitych s_1, ..., s_2N. Ciąg ten oznacza, że i-ta ikona ma wymiary s_i na s_i. Twoim zadaniem jest wyznaczenie najmniejszego pola paska, jakie może zostać osiągnięte.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą N, 1<= N<= 1,000,000. Każdy z kolejnych 2N wierszy zawiera jedną liczbę całkowitą s_i, reprezentującą rozmiar jednej z ikon. Możesz założyć, że 1,000,000>= s_1>= s_2>= ... >= s_2N>0.

Wyjście

Wyjście powinno składać się z jednego wiersza, zawierającego jedną liczbę całkowitą - najmniejsze pole paska.

Przykład

Dla danych:
3
100
99
98
3
2
1

Poprawnym wyjściem jest:
30591

Jednym z optymalnych rozwiązań jest to przedstawione w treści zadania.