문제
KOI 서점에서는 개업 32주년을 맞아 2권의 책을 사면 1권을 공짜로 주는 '2+1 세일'하는 행사를 하고 있다.
KOI 서점은 고객이 구입할 책 3권을 가져 오면 가장 싼 책을 제외하고 나머지 두권의 가격만 받는 형태로 '2+1 세일'을 진행한다.
단, 3권보다 적은 개수를 구매하는 경우에는 세일이 적용되지 않는다.
예를 들어, 7권의 책이 있고 각 가격이 10, 9, 4, 2, 6, 4, 3이고 동현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면
첫 번째 꾸러미에서는 13달러, 두 번째 꾸러미에서는 10달러, 세 번째 꾸러미에서는 9달러이므로 총 32달러 지불하면 된다.
또한 다른 방법으로 (10, 9, 6), (4, 3, 4), (2)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 19달러,
두 번째 꾸러미에서는 8달러, 세 번째 꾸러미에서는 2달러이므로 총 29달러 지불하면 된다.
동현이는 KOI 서점에서 N권의 책을 구입하려고 한다. 동현이가 지불할 최소 금액은 얼마일까?
입력
첫 번째 줄에는 구입할 책의 수 N (1 ≤ N ≤ 100,000)이 주어진다.
두 번째 줄부터 N개의 줄에는 각 책의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어진다.
출력
동현이가 N권의 책을 모두 살 때 필요한 최소비용을 출력한다.
예제1
입력
4
3
2
3
2
출력
8
예제2
입력
6
6
4
5
5
5
5
출력
21
출처
COCI 2015/2016 contest1 2