Background

There was originally an epic and touching background story here, but this space is too small to write it down.

Problem Description

Cirno initially has an empty item sequence and a knapsack of size $V$. You are given $q$ operations of two types:

• add x y: append a new type of item with volume $x$ and value $y$ to the end of the sequence.
• erase: delete the item type at the end of the sequence.

After each operation, you need to compute:

Assuming each item type in the sequence has infinitely many copies, find the maximum total value that can be packed into Cirno’s knapsack.

Input Format

The first line contains two integers $q$ and $V$, representing the number of operations and the knapsack size.

The next $q$ lines each contain one operation.

Output Format

Output $q$ lines. Each line contains the answer after the corresponding operation.

4 10
add 10 3
add 5 2
add 3 3
erase

3
4
9
4

Hint

For $100\%$ of the testdata, $1 \le q, V, x, y \le 2 \times 10^4$.

Translated by ChatGPT 5