Filling the bag P63183


Statement
 

pdf   zip

thehtml

Ali Baba is hidden in the cave of the treasure, watching how the forty thieves leave and take away jewels all the time. When the thieves will depart, Ali Baba will fill his bag with the most valuable jewels, but he will have to make it quickly, so that they cannot catch him. Therefore, at every moment he wants to know which are the jewels that he will have to take when he has the opportunity. Help him!

Input

Input start with n > 0, the number of jewels that fit in the bag. Follow several actions of the thieves, one per line: If they leave a jewel, there is the word “leave” followed by its value. If they take a jewel, there is the word “take” followed by its value. The values of the jewels are natural numbers, all different.

Output

Print a line for each action of the thieves, with the maximum value of the jewels that Ali Baba could take if the thieves left at that moment.

Public test cases
  • Input

    3
    leave 1000
    leave 100
    leave 400
    leave 2000
    take 1000
    leave 50
    leave 3000
    take 100
    take 2000
    leave 1500
    take 400
    take 1500
    

    Output

    1000
    1100
    1500
    3400
    2500
    2500
    5400
    5400
    3450
    4900
    4550
    3050
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++