30091번 - 직사각형 만들기 서브태스크

문제

진흥이는 나무젓가락을 $N$쌍 이용하여 직사각형 두 개를 만들려고 한다. 각 나무젓가락 쌍에는 1ドル$번부터 $N$번까지의 서로 다른 번호가 붙어있고, $i$번 나무젓가락의 길이는 $L_i$이다. 진흥이는 1ドル$부터 $N$번 중 원하는 2ドルM$개의 서로 다른 번호를 고르고, 고른 번호의 나무젓가락을 두 쌍씩 짝짓는다. 짝지은 두 쌍의 나무젓가락마다 한 나무젓가락을 가로로, 다른 나무젓가락을 세로로 하는 직사각형을 만든다.

왼쪽 그림은 길이 5ドル$의 나무젓가락을 가로로, 길이 6ドル$의 나무젓가락을 세로로 하여 직사각형을 만든 모습이다. 오른쪽 그림은 길이 7ドル$의 나무젓가락을 가로로, 길이 4ドル$의 나무젓가락을 세로로 하여 직사각형을 만든 모습이다.

진흥이는 $M$을 원하는 양의 정수로 고를 수 있지만, 짝지은 나무젓가락들로 만든 직사각형의 둘 레는 모두 같아야 한다. 직사각형들의 넓이의 합을 가장 크게 하려면 어떻게 해야 할까?

입력

첫 번째 줄에 나무젓가락의 개수 $N$이 주어진다. (2ドル \le N \le 2,000円$)

두 번째 줄에 $i$번 나무젓가락의 길이 $L_i$가 1ドル$번 나무젓가락부터 $N$번 나무젓가락까지 공백으로 구분되어 주어진다. (1ドル \le L_i \le 10,000円,000円$)

출력

첫 번째 줄에 직사각형들의 넓이 합의 최댓값을 출력한다.

제한

서브태스크

힌트