Yuuka is a person of high status in Gensokyo. She is busy with many affairs and feels that she can no longer manage her tasks. Therefore, she decides to develop a schedule management software to help her manage her tasks.
For each task $i$, there is a corresponding deadline $t_i$ and a profit $p_i$, which means that if Yuuka can complete this task no later than day $t_i$, she can obtain a profit of $p_i$. Yuuka is very capable, and any task can be completed in exactly one day. However, because there are too many tasks, sometimes it is impossible to complete all of them. Thus, Yuuka wants to know the maximum cumulative profit she can obtain by completing tasks under these circumstances.
Since the people in Gensokyo are very fickle, tasks are constantly changing. Yuuka hopes that this management software can also support adding a task and deleting a task.
Specifically, Yuuka wants to support the following 2 operations:
ADD t p: Add a new task with deadline $t$ and profit $p$.DEL t p: Delete a task with deadline $t$ and profit $p$. If there are multiple such tasks, delete only one. The data guarantees that such a task always exists.
After each operation is executed, you need to output the maximum profit that can be obtained from the tasks that can be completed.
Yuuka has a total of $T$ days to arrange, from day 1 to day $T$. Can you help her write this efficient software?
Input
The first line of the input contains two positive integers $T$ and $Q$, representing the number of days and the number of operations, respectively.
The next $Q$ lines each describe an operation. The $i$-th line represents the $i$-th operation, in the form of ADD t p or DEL t p, with the meanings as described above.
Output
For each operation, output an integer representing the maximum profit Yuuka can obtain after executing that operation.
Constraints
For 100% of the data, $1 \le t \le T$, $0 < p \le 10^4$, and $t, p$ are integers.
The characteristics of the test cases are as follows:
| Test Case ID | $T$ | $Q$ | Special Instructions |
|---|---|---|---|
| 1 | $\le 1000$ | $\le 1000$ | None |
| 2 | $\le 10$ | $\le 100000$ | None |
| 3~6 | $\le 100000$ | $\le 100000$ | All operations are ADD |
| 7~8 | $\le 100000$ | $\le 100000$ | All ADD operations occur before all DEL operations |
| 9~10 | $\le 50000$ | $\le 50000$ | None |
| 11~14 | $\le 100000$ | $\le 100000$ | None |
| 15~20 | $\le 300000$ | $\le 300000$ | None |
Examples
Input 1
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
Output 1
5811 10843 5811 11361 14847 9036 3486 8602 18165 18259
Input 2
See app/app.in in the contestant directory.
Output 2
See app/app.ans in the contestant directory.