Description

Youxiang is a very influential person in Gensokyo. She handles a huge number of affairs every day, and it has become hard for her to manage them all. Therefore, she decides to develop a schedule management program to help manage her tasks.

For each task $i$, there is a deadline $t_i$ and a profit $p_i$. If Youxiang finishes this task no later than day $t_i$, she will obtain a profit of $p_i$. Youxiang is very capable and can finish any task in exactly one day. However, since there are so many tasks, she cannot always complete all of them. She wants to know, in such cases, what the maximum total profit she can obtain is.

Since people in Gensokyo are fickle, tasks keep changing. Youxiang wants this management program to support inserting a task and deleting a task.

Specifically, the program should support the following 2 operations:

1. ADD t p: Insert a new task with deadline $t$ and profit $p$.
2. DEL t p: Delete one task with deadline $t$ and profit $p$. If multiple such tasks exist, delete exactly one. It is guaranteed that such a task exists.

After each operation is executed, you need to output the maximum total profit achievable by completing tasks.

Youxiang has $T$ days to schedule, from day $1$ to day $T$. Can you help her write this efficient program?

Input Format

The first line contains two integers $T$ and $Q$, denoting the number of days and the number of operations.

The next $Q$ lines describe the operations. The $i$-th line is the $i$-th operation, in the form ADD t p or DEL t p, with meanings as described above.

Output Format

For each operation, output one integer: the maximum total profit Youxiang can obtain after that operation is performed.

5 10
ADD 1 5811
ADD 3 5032
DEL 3 5032
ADD 3 5550
ADD 5 3486
DEL 1 5811
DEL 3 5550
ADD 4 5116
ADD 3 9563
ADD 5 94

5811
10843
5811
11361
14847
9036
3486
8602
18165
18259

Hint

It is guaranteed that $1 \le T, Q \le 3 \times 10^5$.

$\text{Statement fixed by @Starrykiller.}$

Translated by ChatGPT 5