AT_abc440_f.[ABC440F] Egoism

在 AtCoder 牧场，马匹自己洗澡。有些马洗澡后会清理干净，有些马则会留下一地污渍。

这里有 $N$ 匹马，编号从 $1$ 到 $N$ 。第 $i$ 匹马（$1 \leq i \leq N$）的心情值是 $A_i$ ，整洁度是 $B_i$ （其中 $B_i$ 是 $1$ 或 $2$）。

晚上，$N$ 匹马各洗一次澡。设 $p_j$ 是在第 $j$ 回（$1 \leq j \leq N$）中洗澡的马的编号。马 $p_j$ 的满意度如下：

• 若 $j \geq 2$ ，则为马 $p_j$ 的心情值与马 $p_{j-1}$ 的整洁度的乘积。
• 若 $j = 1$ ，则为马 $p_j$ 的心情值。

在 $Q$ 天中，每天会给出一个询问，请按顺序处理。第 $k$ 天（$1 \leq k \leq Q$）的询问如下：

• 将马 $W_k$ 的心情值改为 $X_k$ ，整洁度改为 $Y_k$ （其中 $Y_k$ 为 $1$ 或 $2$）。修改后，如果可以任意决定 $N$ 匹马洗澡的顺序，求当晚 $N$ 匹马洗澡的最大可能总满意度。

输入内容由标准输入提供，格式如下：

$N$ $Q\\$
$A_1$ $B_1\\$
$\vdots\\$
$A_N$ $B_N\\$
$W_1$ $X_1$ $Y_1\\$
$\vdots\\$
$W_Q$ $X_Q$ $Y_Q$

输出 $Q$ 行。第 $k$ 行（ $1 \leq k \leq Q$ ）应该包含第 $k$ 天的查询答案。

样例解释 #1

对于第一天的查询，如果马匹按照 $3,1,4,2$ 的顺序洗澡，则每匹马的满意度如下：

• 马 $3$ 的满意度为 $3$
• 马 $1$ 的满意度为 $1 \times 1 = 1$
• 马匹 $4$ 的满意度为 $7 \times 2 = 14$
• 马 $2$ 的满意度是 $7 \times 2 = 14$

本例中的总满意度为 $32$ 。

对于第二天的查询，如果马匹按照 $4,2,1,3$ 的顺序洗澡，则每匹马的满意度如下：

• 马 $4$ 的满意度为 $7$
• 马 $2$ 的满意度是 $7 \times 2 = 14$
• 马匹 $1$ 的满意度为 $3 \times 1 = 3$
• 马 $3$ 的满意度是 $3 \times 1 = 3$

本例中的总满意度为 $27$。

对于第三天的查询，如果马匹按照 $4,3,2,1$ 的顺序洗澡，则总满意度为 $18$。

对于第四天的查询，如果马匹洗澡的顺序为 $4,3,1,2$ ，则总满意度为 $2000015$。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^6$
• $B_i$ 是 $1$ 或 $2$。
• $1 \leq W_k \leq N$
• $1 \leq X_k \leq 10^6$
• $Y_k$ 是 $1$ 或 $2$。
• 所有输入值均为整数。