Peluixos gegants P92166

0.55 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.

0.45

Els propietaris de l’empresa que ven aquests ossos estan encantats amb en Philippe, així que han decidit fer-li una oferta $3 \times 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 $10^4$. Podeu suposar $0 \le n \le 10^5$.

Sortida

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