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?
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.
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.
Uma linha contendo um inteiro, que corresponde ao menor custo a pagar pelo cliente para levar todos os livros.
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 | --- |
4 3 2 3 2
8
É 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).
6 6 4 5 5 5 5
21
É possível criar os grupos (6,4,5) e (5,5,5), que formam a melhor combinação possível.