Rei i joies P58851

El tresor d’un país llunyà és inicialment buit. Després, els funcionaris del tresor adquireixen algunes joies (cadascuna amb un cert valor) i les afegeixen al tresor d’una en una.

Segons una tradició antiga, el rei d’aquell país té el dret d’escollir i quedar-se fins a dos terços de les joies. Com que el rei pot haver de fugir del país en qualsevol moment, sempre necessita saber de forma eficient el valor màxim total de les joies que es pot endur. El podeu ajudar?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb un natural n, el nombre de joies adquirides pel tresor. Segueixen els n valors de les joies, en l’ordre en què s’obtenen. Podeu assumir 1 ≤ n ≤ 10⁴, i que els valors són enters entre 1 i 10⁹.

Sortida

Per a cada cas, i després de cada joia adquirida, escriviu el valor màxim total de les joies que el rei pot triar. Escriviu una línia amb 10 guions després de cada cas.