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

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

왼쪽 그림은 길이 $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$)

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