Under construction

Still being built. Things may change

Homework Never Ends!

Interview

Time limit2sMemory limit256 MB

Summary
Each minute either adds homework (value A, work time T) or nothing; a new task preempts the current one, and finished tasks are submitted at the minute they finish. Sum the values of tasks completed within N minutes.
Level

Medium4 of 10

Topics
Stack, Simulation, Implementation, Array
Solved
No attempts yet

Problem

Seongae is taking a very heavy load of major courses this semester. Because of that, she spends almost every day doing homework. Even so, the homework shows no sign of letting up, because new homework is added by the minute. Fortunately, all homework is due at the end of the semester. Driven up the wall by so much homework, Seongae works through it by the following rules.

  1. She does homework in the order it was most recently assigned. She also starts a homework assignment as soon as she receives it.
  2. If a new homework assignment appears while she is working on one, she stops the current one and moves to the new one.
  3. When the new homework is finished, she resumes the previous homework from the point where she left off. Seongae has a good memory, so no matter how much time passes she can remember exactly where she was.

As soon as Seongae receives a homework assignment, she knows exactly how many minutes it will take, and any homework she submits always receives full marks.

Seongae wants to predict the homework score she will earn this semester. But even now, while she is trying to predict it, new homework keeps arriving, so she has no room to relax. Help Seongae figure out the homework score she will earn!

Input

The first line gives the integer N, the length of this semester in minutes. (1 ≤ N ≤ 1,000,000)

The following N lines, starting from the second line, give the homework information at minute 1 through minute N of the semester in one of the two forms below.

  • 1 A T: the homework is worth A points in total, and it takes Seongae T minutes to finish it. Both A and T are integers. (1 ≤ A ≤ 100, 1 ≤ T ≤ 1,000,000)
  • 0: no homework was given at that point in time.

Output

Print the homework score Seongae will earn.

Examples2

  1. Example 1

    Input
    3
1 100 3
0
0
    Expected output
    100

  2. Example 2

    Input
    5
1 10 3
0
1 100 2
1 20 1
0
    Expected output
    120