AT_abc440_f [ABC440F] Egoism

> At AtCoder Ranch, horses bathe themselves. Some horses clean up afterward, while others leave a mess. There are $ N $ horses, numbered $ 1 $ to $ N $ . Horse $ i $ ( $ 1 \leq i \leq N $ ) has a **mood** $ A_i $ and a **tidiness** $ B_i $ (where $ B_i $ is $ 1 $ or $ 2 $ ). At night, the $ N $ horses bathe once each. Let $ p_j $ be the number of the horse that bathes in the $ j $ -th turn ( $ 1 \leq j \leq N $ ). The **satisfaction** of horse $ p_j $ is given as follows: - If $ j \geq 2 $ , the product of the mood of horse $ p_j $ and the tidiness of horse $ p_{j-1} $ . - If $ j = 1 $ , the mood of horse $ p_j $ . You will be given $ Q $ queries, one for each day over $ Q $ days. Process them in order. The query for the $ k $ -th day ( $ 1 \leq k \leq Q $ ) is as follows: - Change the mood of horse $ W_k $ to $ X_k $ and its tidiness to $ Y_k $ (where $ Y_k $ is $ 1 $ or $ 2 $ ). Then, find the maximum possible total satisfaction of the $ N $ horses' baths that night if you can decide the order in which the $ N $ horses bathe arbitrarily.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_N $ $ B_N $ $ W_1 $ $ X_1 $ $ Y_1 $ $ \vdots $ $ W_Q $ $ X_Q $ $ Y_Q $

Output $ Q $ lines. The $ k $ -th line ( $ 1 \leq k \leq Q $ ) should contain the answer to the query for the $ k $ -th day.

### Sample Explanation 1 For the query on the first day, if the horses bathe in the order $ 3,1,4,2 $ , the satisfaction of each horse is as follows: - Horse $ 3 $ 's satisfaction is $ 3 $ - Horse $ 1 $ 's satisfaction is $ 1 \times 1 = 1 $ - Horse $ 4 $ 's satisfaction is $ 7 \times 2 = 14 $ - Horse $ 2 $ 's satisfaction is $ 7 \times 2 = 14 $ The total satisfaction in this case is $ 32 $ . For the query on the second day, if the horses bathe in the order $ 4,2,1,3 $ , the satisfaction of each horse is as follows: - Horse $ 4 $ 's satisfaction is $ 7 $ - Horse $ 2 $ 's satisfaction is $ 7 \times 2 = 14 $ - Horse $ 1 $ 's satisfaction is $ 3 \times 1 = 3 $ - Horse $ 3 $ 's satisfaction is $ 3 \times 1 = 3 $ The total satisfaction in this case is $ 27 $ . For the query on the third day, if the horses bathe in the order $ 4,3,2,1 $ , the total satisfaction is $ 18 $ . For the query on the fourth day, if the horses bathe in the order $ 4,3,1,2 $ , the total satisfaction is $ 2000015 $ . ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^6 $ ( $ 1 \leq i \leq N $ ) - $ B_i $ is $ 1 $ or $ 2 $ . ( $ 1 \leq i \leq N $ ) - $ 1 \leq W_k \leq N $ ( $ 1 \leq k \leq Q $ ) - $ 1 \leq X_k \leq 10^6 $ ( $ 1 \leq k \leq Q $ ) - $ Y_k $ is $ 1 $ or $ 2 $ . ( $ 1 \leq k \leq Q $ ) - All input values are integers.