Cirno's Infinite Knapsack

Cirno starts with an initially empty sequence of items and a backpack of size $V$. There are $q$ operations, each being one of the following:

• add x y: Append an item with volume $x$ and value $y$ to the sequence.
• erase: Remove the last item from the sequence.

After each operation, you are required to find the maximum total value that can be obtained by filling the backpack of capacity $V$, under the following condition: for every type of item present in the sequence, there are infinitely many copies available. In other words, if the current sequence contains items with volumes $x_i$ and values $y_i$, determine the maximum total value achievable subject to the constraint

$$\sum_{i} x_i \cdot k_i \le V,$$

where each $k_i\ge 0$ is an integer. This can be computed using an unbounded knapsack formulation with the recurrence

$$\text{dp}[j] = \max_{i \text{ such that } j \ge x_i}\{\text{dp}[j-x_i] + y_i\}, \quad 0 \le j \le V, $$

with the initial condition $\text{dp}[0]=0$.

inputFormat

The first line contains two integers $V$ and $q$, representing the backpack capacity and the number of operations respectively. Each of the following $q$ lines describes an operation in one of the two formats:

• add x y: Add an item with volume $x$ and value $y$.
• erase: Erase the last added item.

outputFormat

After each operation, output a single integer: the maximum total value obtainable by filling the backpack of capacity $V$ with an unlimited supply of each item type present in the sequence. Print each answer on a separate line.

sample

5 5
add 1 2
add 2 3
erase
add 2 2
add 3 4

10
10
10
10
10

</p>