题目背景

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

目前提交可能会出现 100pts WA 的情况，在修了，在修了。

题目描述

苏联餐厅前有 $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$ 个整数表示用餐的顺序。

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

提示

数据范围

对于 $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$		$13$
$3$	$2\times 10^5$			$21$
$4$		$2\times 10^5$	B	$29$
$5$				$32$

• 特殊性质 A：只有 $\texttt{POREDAK}$ 事件。
• 特殊性质 B：没有 $\texttt{POREDAK}$ 事件。