Background

Translated from Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection) D2T2。$\texttt{2s,0.5G}$。

Problem Description

There are $N$ people queuing in front of a Soviet restaurant, numbered $1 \sim N$ in order.

There is only one dish in the restaurant, and it is also the signature dish—fried eggs. There is no chef in the restaurant, so the food is cooked by the customers themselves.

Due to limited equipment, at any moment, at most one person can cook, and at any moment, at most one person can eat.

Define the “total dining time” as the time needed from when the first person starts preparing food to when the last person finishes eating.

Cooking and eating do not have to follow the queue order; a customer who cooks earlier may eat later.

Person $i$ has cooking time $a_i$ and eating time $b_i$. You need to find the minimum possible total dining time under an optimal arrangement.

In addition, there are $M$ events:

• $\texttt{DOLAZI a b}$: A new customer arrives, with cooking time $a$ and eating time $b$. Suppose this is the $i$-th arriving new customer, then their number is $(N+i)$.
• $\texttt{ODLAZI x}$: Customer $x$ leaves the queue.
• $\texttt{POREDAK}$: The customers are very impatient and want to know the optimal strategy that makes the total dining time as short as possible.

For the first two types of events, you need to output the minimum total dining time after the event ends.

For the third type of event, you need to output the best cooking order and eating order at that moment.

Input Format

The first line contains two positive integers $N, M$.

The next $N$ lines: the $i$-th line contains two positive integers $a_i, b_i$.

The next $M$ lines: each line describes an event.

The testdata guarantees that all events are valid, and at every moment there is at least one customer.

Output Format

Output $(M+1)$ lines.

The first line outputs the minimum total dining time initially.

Then for the next $M$ lines, for the $i$-th line:

• If the $i$-th event is $\texttt{DOLAZI}$ or $\texttt{ODLAZI}$, output one integer, the minimum total dining time after this event ends.
• Otherwise, suppose there are currently $k$ customers, output $2k$ integers describing an optimal strategy: the first $k$ integers are the cooking order, and the last $k$ integers are the eating order.

2 1
1 3
2 3
POREDAK

7
1 2 1 2

1 4
4 3
DOLAZI 3 8
DOLAZI 5 2
ODLAZI 1
ODLAZI 3

7
14
16
13
11

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $1 \le N, M \le 2 \times 10^5$；
• $1 \le a_i, b_i, a, b \le 10^9$；
• All events are valid, and at every moment there is at least one customer；
• There are at most $\bf 10$ $\texttt{POREDAK}$ events.

• Special Property A: Only $\texttt{POREDAK}$ events.
• Special Property B: There are no $\texttt{POREDAK}$ events.

Translated by ChatGPT 5