题面描述

你作为一名正统流派的魔法师，你需要去研究一些魔法书去增强你魔法的威力。

你有一个书柜，一开始为空。但是你可以不停地去魔法师图书馆借取一些魔法书或是归还一些书籍来维护你的书柜。

对于你当前的书柜里面，有若干本书，每本书有两个属性: $t_i$ 表示书的类别，$p_i$ 表示该魔法书的威力。

但是你的学习能力有限，这要求你只能从书柜里面挑出若干本书进行学习，并满足如下两个性质。

1.你最多只能学习 $n$ 本书。

2.同时对于类别为 $t$ 的书，你也最多只能学习 $t$ 本书。

然后你施展魔法的威力便是你学习的这些书威力的总和。

书柜起始为空，然后你有一些从图书馆借取和归还的操作记录。你需要求出每一次和图书馆交互完毕后，你能从通过当前书柜，能学习到的最大的魔法威力。

输入格式

第一行包括两个正整数 $n, m$, 分别表示你能学习的书数量的上限以及从图书馆借取和归还的事件数。

之后 $m$ 行每行包括一个形式为 $op$ $t$ $p$ 的输入：

若 $op$ 为 "BORROW"，则表示从图书馆借取了一本类别为 $t$，威力为 $p$ 的魔法书加入到你的书柜；

若 $op$ 为 "RETURN"，则表示从书柜里拿出，并向图书馆归还一本类别为 $t$，威力为 $p$ 的魔法书。（可能会有相同类别和威力的书，任意归还一本即可）。

输出格式

一共 $m$ 行，每行包括一个非负整数。表示事件结束后能学习到的最大的魔法威力。

样例

输入1

5 10 
BORROW 1 3725
BORROW 3 3867
RETURN 3 3867
BORROW 3 4440
BORROW 5 2155
RETURN 1 3725
RETURN 3 4440
BORROW 4 4098
BORROW 3 7942
BORROW 5 777

输出1

3725
7592
3725
8165
10320
6595
2155
6253
14195
14972

输入2

见测试样例下载

输出2

见测试样例下载

数据规模

对于 $5\%$ 的数据: $1 \leq t,N,M \leq 50$

对于 $10\%$ 的数据：$1 \leq t,N,M \leq 100$。

对于 $30\%$ 的数据：$1 \leq t,N,M \leq 10000$。

另包含 $30\%$ 的数据：$1 \leq p \leq 1000$

对于 $100\%$ 的数据: $1 \leq t,N,M \leq 300000, 1 \leq p \leq 10^9$。

另外，总共包含 $30\%$ 的数据，满足没有 $RETURN$ 操作。且这部分数据均匀分布。

注意本题时空限制不同：

时间限制：2S

空间限制：1024MB