P5391 [Cnoi2019] Cirno’s Dyed Heart

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

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.

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 $q$ lines. Each line contains the answer after the corresponding operation.

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