P11027 [COTS 2020] 餐厅 Restoran

译自 [Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2020/) D2T2。$\texttt{2s,0.5G}$。

苏联餐厅前有 $N$ 个人在排队，按顺序标号 $1\sim N$。 餐厅内只有一种菜，同时也是招牌菜——煎蛋。餐厅内没有厨师，所以食物由客人自己烹饪。 由于设备有限，**同一时刻最多有一个人可以烹饪，同一时刻最多有一个人可以用餐。** 定义：「用餐总时间」为从第一个人开始准备食物，到最后一个人用完餐，需要的时间。 烹饪和用餐不一定按顺序，先烹饪的客人可以后用餐。 第 $i$ 个人的烹饪时间为 $a_i$，用餐时间为 $b_i$。你需要求出最优情况下，用餐总时间的最小值。 此外，还有 $M$ 个事件： - $\texttt{DOLAZI a b}$：新来了一位新客人，他的烹饪时间为 $a$，用餐时间为 $b$。设这是第 $i$ 位新来的客人，则标号为 $(N+i)$。 - $\texttt{ODLAZI x}$：第 $x$ 位客人离开队伍。 - $\texttt{POREDAK}$：客人很不耐烦，想要知道最优的策略，使得用餐总时间最短。 对于前两个类型的事件，你需要求出这个事件结束后，用餐总时间的最小值； 对于第三个类型的事件，你需要求出此时最佳的烹饪、用餐顺序。

第一行，两个正整数 $N,M$。 接下来 $N$ 行，第 $i$ 行两个正整数 $a_i,b_i$。 接下来 $M$ 行，每行描述一个事件。 数据保证事件合法，且每一时刻至少存在一名客人。

输出 $(M+1)$ 行。 第一行，输出初始时用餐总时间的最小值。 接下来 $M$ 行，对于第 $i$ 行： - 若第 $i$ 个事件为 $\texttt{DOLAZI}$ 或 $\texttt{ODLAZI}$ ，输出一个整数，表示这个事件结束后，用餐总时间的最小值； - 否则，设当前有 $k$ 个客人，输出 $2k$ 个整数，描述最优策略：前 $k$ 个整数表示烹饪的顺序，后 $k$ 个整数表示用餐的顺序。

#### 数据范围 对于 $100\%$ 的数据，保证： - $1\le N,M\le 2\times 10^5$； - $1\le a_i,b_i,a,b\le 10^9$； - 事件合法，且每一时刻至少存在一名客人； - **$\texttt{POREDAK}$ 事件最多只有 $\bf 10$ 个。** | 子任务编号 | $N\le $ | $M\le $ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | :--: | | $ 1 $ | $9$ | $ 1 $ | A | $ 5 $ | | $ 2 $ | $20$ | $1$ | A | $ 13 $ | | $ 3 $ | $2\times 10^5$ | $1$ | A | $ 21 $ | | $ 4 $ | $2\times 10^5$ | $2\times 10^5$ | B | $ 29 $ | | $ 5 $ | $2\times 10^5$ | $2\times 10^5$ | | $ 32 $ | - 特殊性质 A：只有 $\texttt{POREDAK}$ 事件。 - 特殊性质 B：没有 $\texttt{POREDAK}$ 事件。