Problema B - Promoção na Livraria

Existe uma oferta promocional numa livraria: "leve 3, pague os 2 mais caros". Assim, se um cliente comprar 3 livros, ele recebe o mais barato de graça. O cliente pode no entanto querer comprar um número ainda maior de livros e, dependendo da maneira como os combinar em grupos de três, recebe de graça o mais barato de cada grupo.

Por exemplo, supõe que os livros que o cliente comprou têm os seguintes preços: 10 3 2 4 6 4 9. Se o cliente os combinar nos grupos (10,3,2), (4,6,4) e (9), ele receberá grátis um livro de preço 2 (do 1º grupo) e um livro de preço 4 (do 2º grupo). Não receberá de graça nenhum livro do 3º grupo, porque esse grupo apentas contém um livro.

O dono do livraria está cheio de boas intenções e quer sempre fazer o cliente pagar a menor quantia possível. Será que podes ajudá-lo?

O Problema

Dado o número de livros que o cliente quer comprar, e o preço de cada um, a tua tarefa é determinar qual o custo mínimo que o cliente deve pagar, se os livros foram combinados em grupos de melhor forma possível.

Nota que não és obrigado a formar grupos todos com tamanho 3, mas o número de livros em cada grupo deve ser entre 1 e 3, inclusive.

Input

A primeira linha de input contém um inteiro N, o número de livros que o cliente quer comprar.

Seguem-se N linhas, cada uma contendo um inteiro Pi indicando o preço de cada livro.

Output

Uma linha contendo um inteiro, que corresponde ao menor custo a pagar pelo cliente para levar todos os livros.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ N ≤ 100 000   Quantidade de livros a comprar
1 ≤ Pi ≤ 100 000   Preço de cada livro

Os casos de teste deste problema estão organizados em 2 grupos com restrições adicionais diferentes:

Grupo Nº de Pontos Restrições adicionais
1 50 1 ≤ N ≤ 2 000
2 50 ---

Input de Exemplo 1

4
3
2
3
2	

Output de Exemplo 1

8

Explicação do Exemplo 1

É possível criar os grupos (3,2,2) e (3), que é a melhor combinação possível, levando a um custo de 3+2+3=8 (um livro de preço 2 é oferecido de graça no 1º grupo).

Input de Exemplo 2

6
6
4
5
5
5
5	

Output de Exemplo 2

21

Explicação do Exemplo 2

É possível criar os grupos (6,4,5) e (5,5,5), que formam a melhor combinação possível.


1º Concurso de Treino das ONI'2020
(05/04 a 07/04 de 2020)