시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 10 4 (40%) 4
문제
시간 제한 1초, 메모리 제한 32MB 서점에서 "3개를 그중 비싼 2개 값으로 가져가세요."라는 할인 행사를 하고 있다. 즉, 고객이 3개의 책을 고르면 그중 가장 저렴한 책은 공짜로 가져가는 것이다. 물론 고객들은 더 많은 책을 가져갈 수도 있고 그 책들을 3개짜리 묶음으로 어떻게 나누냐에 따라서 각 묶음에서 가장 저렴한 책은 공짜로 가져가게 된다. 예를 들면 고객이 고른 책들의 가격이 $10, 3, 2, 4, 6, 4, 9$라고 하자. 만약 그가 그 책들을 $(10, 3, 2), (4, 6, 4), (9)$와 같이 묶음으로 만들었다면 그는 첫 번째 묶음에서 가격 2짜리, 두 번째 묶음에서 가격 4짜리 책을 공짜로 가져가게 된다. 세 번째 묶음에는 책이 하나밖에 없기 때문에 공짜로 가져갈 것이 없다. 서점에서 일하는 한 여직원은 선의를 가지고 모든 고객들에게 최대한 할인을 해주고자 한다. 주어진 책들의 가격을 보고 이들의 묶음을 만드는 최선의 방법을 찾아서 총 지불 가격을 최소화 시키는 프로그램을 작성하라. 참고: 모든 묶음들이 정확하게 3개의 책을 가지고 있을 필요는 없다, 하지만 1개 이상 3개 이하의 조건은 만족시켜야 한다.
입력
첫째 줄에 고객이 산 책의 개수 $N(1 ≤ N ≤ 100,000)$이 주어진다. 다음 $N$개의 줄에는 책의 가격인 $C_i(1 ≤ C_i ≤ 100,000)$가 주어진다.
출력
첫째 줄에 가능한 최소 지불 가격을 출력한다.
힌트
#### 점수 - 50%의 경우에 $N ≤ 2,000$이다. #### 예제 입력 1 ``` 4 3 2 3 2 ``` #### 예제 출력 1 ``` 8 ``` #### 예제 입력 2 ``` 6 6 4 5 5 5 5 ``` #### 예제 출력 2 ``` 21 ``` #### 예제 설명 1 - $(3,2,2), (3)$으로 묶으면 가장 저렴한 조합이 된다. #### 예제 설명 2 - $(6,4,5), (5,5,5)$로 묶으면 가장 저렴한 조합이 된다.