Peluixos gegants P92166


Statement
 

pdf   zip

thehtml
L’expedició de l’UPC a París va ser rebuda per uns simpàtics (i gegants!) ossos de peluix com els de la fotografia. Aquells ossos eren per tot arreu: a les botigues, als restaurants i fins i tot als hotels! Aquesta agradable invasió va ser provocada per un llibreter de la zona, de nom Philippe, a qui li va semblar una gran idea comprar els ossos i regalar-los a les botigues.

Els propietaris de l’empresa que ven aquests ossos estan encantats amb en Philippe, així que han decidit fer-li una oferta 3 × 2: cada vegada que compri 3 ossos, el més barat li sortirà de franc (un d’ells, en cas d’empat). Per exemple, si els preus són de 7, 7 i 9 euros, en Philippe només pagarà 16 euros.

En Philippe té una llista de preus de 3n ossos que vol comprar a partir d’ara. Ara bé, no sap com agrupar els ossos per tal de minimitzar el cost total. El podeu ajudar?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, seguit de 3n enters amb el preu de cada ós, tots entre 1 i 104. Podeu suposar 0 ≤ n ≤ 105.

Sortida

Per a cada cas, escriviu el preu mínim que haurà de pagar en Philippe.

Public test cases

  • Input

    1  7 7 9
0
3  42 23 17 23 42 100 100 100 1

    Output

    16
0
324
    • Information
    Author
    Martí Oller
    Language
    Catalan
    Official solutions
    C++ Python Python
    User solutions
    C++ Python