U123379 4270. 【NOIP2015模拟10.27】魔道研究

### [题解](https://www.cnblogs.com/wondering-world/p/13378097.html)

“我希望能使用更多的魔法。不对，是预定能使用啦。最终我要被大家称呼为大魔法使。为此我决定不惜一切努力。” ——《$The$ $Grimoire$ $of$ $Marisa$》雾雨魔理沙 魔理沙一如既往地去帕秋莉的大图书馆去借魔导书($Grimoire$) 来学习魔道。 最开始的时候，魔理沙只是一本一本地进行研究。然而在符卡战中，魔理沙还是战不过帕秋莉。 好在魔理沙对自己的借还和研究结果进行了记录，从而发现了那些魔导书的精妙之处。 帕秋莉的那些魔导书，每本都有一个类别编号$t_i$ 和威力大小$p_i$。而想要获得最有威力的魔法，就必须同时研究一些魔导书。而研究的这些魔导书就必须要满足，类别编号为$T$ 的书的本数小于等于$T$，并且总共的本数小于等于一个给定的数$N$。而研究这些魔导书之后习得的魔法的威力就是被研究的魔导书的威力之和。 为了击败帕秋莉，魔理沙想要利用自己发现的规律来获得最有威力的魔法。 她列出了计划中之后$M$ 次的借还事件，并想要知道每个事件之后自己所能获得的魔法的最大威力。可她忙于魔法材料——蘑菇的收集，于是这个问题就交给你来解决了。

第$1$行$2$个整数$N,M$，分别表示魔理沙能研究的魔导书本数的上限和她的借还事件数。 之后$M$行，每行的形式为“$op$ $t$ $p$”（不含引号）。$Op$ 为“$BORROW$” 或“$RETURN$”，分别表示借书和还书。 $T$ 为一个整数，表示这本书的类别编号。$P$为一个整数，表示这本书的威力大小。 注意，还书时如果有多本书满足类别编号为$t$，威力大小为$p$，这表明这些书都是相同的，魔理沙会任选其中一本书还回去。如果你问我为何会有相同的书，多半因为这是魔导书吧。

一共$M$行，每行一个整数，即每个事件之后的最大威力。

对于$5\%$ 的数据，$1 \le t,N,M \le 50$。 对于$10\%$ 的数据，$1 \le t,N,M \le 100。$ 对于$30\%$ 的数据，$1 \le t,N,M \le 10 000$。 另有$30\% $的数据，$1 \le p \le 1 000$。 对于$100\% $的数据，$1 \le t,N,M \le 300 000,1 \le p \le 1 000 000 000$。 另外，总共有$30\%$ 的数据，满足没有“$RETURN$” 操作。这部分数据均匀分布。