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$。 - 所有输入值均为整数。