Problema número 650

Oferta 3×2

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Libros en oferta

En mi librería favorita, un día al año sacan una oferta de 3×2: por cada tres libros que compras te regalan uno, el de menor precio. Yo espero ansioso a que llegue ese día y entonces compro todos los libros que puedo.

El año pasado compré libros que valían 40, 35, 30, 25, 20, 15 y 10 euros, por los que pagué 150 euros, obteniendo un descuento total de 25 euros, ya que la librería utiliza un sistema estricto (¡y muy ventajoso para ella!) a la hora de seleccionar los libros que te regala: son siempre los de menor precio del lote.

Pero después me di cuenta de que si hubiera ido a comprar varias veces podría haber obtenido un descuento mayor. Por ejemplo, si primero hubiera comprado los libros con precios 40, 35, 30 y 25, me habrían regalado el de 25, y al comprar después el resto me hubieran regalado el que valía 10, obteniendo un descuento total de 35 euros.

¿Puedes ayudarme a decidir cómo debería comprar los libros que quiero este año para ahorrarme lo máximo posible?

Entrada

El programa deberá encontrar la solución a diferentes casos de prueba. Cada caso consta de dos líneas. En la primera aparece el número (entre 1 y 1.000) de libros que quiero comprar. En la segunda aparecen los precios de los libros (entre 1 y 10.000), separados por espacios.

Salida

Para cada lote de libros se escribirá el descuento máximo que puedo obtener si me aprovecho de repartirlos en varias compras.

Entrada de ejemplo

7
40 35 30 25 20 15 10
3
50 10 30
2
25 20

Salida de ejemplo

45
10
0