Dynamic Task Scheduling

You are given a schedule management problem. In the fantasy world of Gensokyo, Youkai Youkour (幽香) has many tasks to complete. Each task i has a deadline \(t_i\) and a profit \(p_i\); if the task is finished on or before day \(t_i\), she earns \(p_i\) profit. Each task takes exactly one day to complete and no two tasks can be done on the same day.

However, tasks evolve dynamically. You need to support the following two operations:

1. ADD t p: Add a new task with deadline t and profit p.
2. DEL t p: Remove one occurrence of a task with deadline t and profit p. It is guaranteed that such a task exists.

There are a total of T days available (from day 1 to day T). After each operation, output the maximum total profit that can be achieved by scheduling a subset of tasks (each task is scheduled on a unique day and must be completed by its deadline).

The optimal scheduling is determined by a greedy strategy using a union‐find (disjoint set union) approach: sort tasks in descending order of profit, and for each task, if there is a free day available (no later than its deadline), assign the task to the latest available day. Use the union-find technique to efficiently manage the available days.

Note: All formulas are expressed in \( \LaTeX \) format.

inputFormat

The first line contains two integers T and Q, where T (\(1 \le T \le \text{some limit}\)) is the total number of days, and Q is the number of operations.

Each of the next Q lines contains an operation in one of the following two formats:

• ADD t p: Add a task with deadline t and profit p.
• DEL t p: Delete one occurrence of a task with deadline t and profit p (it is guaranteed to exist).

outputFormat

After each operation, print a single line containing a single integer — the maximum total profit achievable by scheduling tasks on different days such that each task is completed on or before its deadline.

sample

5 5
ADD 3 10
ADD 2 5
ADD 4 7
DEL 2 5
ADD 3 6

10
15
22
17
23