King and jewels P58851


Statement
 

pdf   zip

html

The treasure of a country far away is initially empty. Afterwards, the officials of the treasure acquire some jewels (each one with some value) and add them to the treasure one by one.

According to an old tradition, the king of that country has the right to choose and keep for himself up to two thirds of the jewels. Since the king may need to run away from the country at any moment, he always needs to know in an efficient way the maximum total value of the jewels that he can take with him. Can you help the king?

Input

Input consists of several cases. Every case begins with the number n of jewels acquired by the treasure. Follow the value of the n jewels, in the order in which they are obtained. Assume 1 ≤ n ≤ 104, and that the values are integer numbers between 1 and 109.

Output

For every case, and after every acquired jewel, print the maximum total value of the jewels that the king can choose. Print a line with 10 dashes after every case.

Public test cases

  • Input

    6
10
42
20
23
1000
15

8
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

8
7
7
6
6
7
7
6
6

    Output

    0
42
62
65
1065
1085
----------
0
1000000000
2000000000
2000000000
3000000000
4000000000
4000000000
5000000000
----------
0
7
14
14
21
28
28
34
----------
    • Information
    Author
    Salvador Roura
    Language
    English
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++