XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: 3por2.x, onde x deve ser c, cpp, java, js ou py

Três por Dois

Uma loja de chocolates está fazendo uma promoção do tipo "leve três pague dois". Mais precisamente, você pode escolher quaisquer três chocolates da loja e paga apenas pelos dois mais caros que escolher, levando o mais barato gratuitamente. Se você levar mais do que três chocolates, você pode agrupá-los em grupos de três e levar o chocolate mais barato de cada grupo gratuitamente.

Por exemplo, se você escolher chocolates de preços (em reais) 8, 5, 10, 2, 5, 10 e 4, você pode agrupá-los como (8,5,10), (2,5,10) e (4), pagará um total de (10+8) + (10+5) + 4, ou seja, 37 reais. Mas você pode agrupá-los de uma forma melhor e assim conseguir pagar menos. Você consegue ver como?

Dados os preços dos chocolates escolhidos, escreva um programa para determinar o menor preço a pagar.

Entrada

A primeira linha da entrada contém um inteiro N, o número de chocolates escolhidos. Cada uma das N linhas seguintes contém um número inteiro P, o preço de um chocolate escolhido.

Saída

Seu programa deve produzir uma única linha, contendo um único número inteiro, o menor preço a pagar pelos chocolates escolhidos.

Restrições

  • 1 ≤ N ≤ 100000
  • 1 ≤ P ≤ 1000

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 50 pontos, N ≤ 1000.

Exemplos

Entrada
4
5
6
6
5
Saída
17
	

 

Entrada
4
3
3
3
3
Saída
9
	

 

Entrada
6
7
8
7
7
5
7
Saída
29
	

 

Entrada
7
8
5
10
2
5
10
4
Saída
32
	

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação