슬라임 합치기

면접 대비

시간 제한2초메모리 제한512 MB

요약

슬라임 N개를 둘씩 합치며 합쳐진 크기의 곱만큼 점수를 얻을 때 최대 총점을 구합니다.

문제

영선이와 효빈이가 슬라임 합치기 게임을 한다. 두 사람은 매번 슬라임 두 개를 골라 하나로 합치고, 슬라임이 하나만 남으면 게임이 끝난다.

모든 슬라임의 크기는 양수다. 크기가 $x$ 인 슬라임과 크기가 $y$ 인 슬라임을 합치면 크기가 $x+y$ 인 슬라임 하나가 되고, 합칠 때마다 두 사람은 $x \times y$ 점을 얻는다.

영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 슬라임의 개수 $N$ ( $2 \le N \le 100$ )이 주어진다.

둘째 줄에 슬라임 $N$ 개의 크기가 공백으로 구분되어 주어진다. 크기는 $100$ 이하의 자연수다.

첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다.