[Cnoi2019] 青染之心

题目背景

这里原本有着一个史诗般的可歌可泣的背景故事,可是这里空太小,写不下。

题目描述

Cirno初始有一个空的物品序列,一个大小为 $V$ 的背包,现在你有 $q$ 个操作,分为两种: - add x y : 表示加入一种体积为 $x$, 价值为 $y$ 的物品到序列末尾。 - erase : 表示删除序列末尾的物品。 在每个操作结束以后,你需要求出 : 假设序列中的每种物品都有无穷多个,Cirno的背包可以装下的物品最大价值和。

输入输出格式

输入格式


第一行,两个整数, $q$,$V$ 表示 操作数 和 背包大小。 以下 $q$ 行,每行一个操作。

输出格式


$q$ 行,每行表示每次操作后的答案。

输入输出样例

输入样例 #1

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

输出样例 #1

3
4
9
4

说明

对于 $100\%$ 的数据 $1\le q, V, x, y \le 2\times10^4 $