P11359 [eJOI 2023] Team Building

You need to gather a team of $N$ people. The $i$-th person has an ability value $s_i$. You may add people to your team one by one, in any order. In your team, each person has two additional attributes: Star Talk and Cuteness. Adding a person consists of three steps: - This person enters the team, and both their Star Talk and Cuteness are $0$. - For all remaining people, their Star Talk increases by their own Cuteness. - For all remaining people, their Cuteness increases by the ability value of the newly added person. In the end, the total Star Talk value of your team is defined as the sum of everyone’s Star Talk values. You need to maximize the total Star Talk value. For example, if you add people with ability values $0,2,2,3$ in this order, the changes of everyone’s attributes are as follows: |Action|Star Talk|Cuteness| |:-:|:-:|:-:| |Add the first person|$0$|$0$| |Add the second person|$0,0$|$0,0$| |Update Star Talk|$0,0$|$0,0$| |Update Cuteness|$0,0$|$\textbf{2},0$| |Add the third person|$0,0,0$|$2,0,0$| |Update Star Talk|$\textbf{2},\textbf{0},0$|$2,0,0$| |Update Cuteness|$2,0,0$|$\textbf{4},\textbf{2},0$| |Add the fourth person|$2,0,0,0$|$4,2,0,0$| |Update Star Talk|$\textbf{6},\textbf{2},\textbf{0},0$|$4,2,0,0$| |Update Cuteness|$6,2,0,0$|$\textbf{7},\textbf{5},\textbf{3},0$| At this point, the total Star Talk value is $6+2+0+0=8$. However, if you change the order to $2,2,3,0$, you can get $7+3+0+0=10$. You also need to process $Q$ modifications. Each modification changes the ability value of person $x_i$ to $y_i$. You need to output the maximum total Star Talk value after each modification. The modifications are not independent, meaning each modification is kept for the next one.

The first line contains two integers $N,Q$. The second line contains $N$ integers $s_i$. The next $Q$ lines each contain two integers $x_i,y_i$.

Output $Q+1$ lines. Each line contains one integer, representing the answer for the initial sequence and after each modification.

**Sample Explanation** The optimal plan for the original sequence has already been given in the statement. After the first modification, the sequence becomes $(2,4,2,3)$. After the second modification, the sequence becomes $(2,4,2,0)$. **Constraints** **This problem uses bundled testdata.** - Subtask 1 (11 pts): $N\leq 7$, $Q\leq 100$. - Subtask 2 (19 pts): $N,Q\leq 500$. - Subtask 3 (15 pts): $Q\leq 10$. - Subtask 4 (6 pts): $s_i,y_i\leq 1$. - Subtask 5 (9 pts): $s_i,y_i\leq 500$. - Subtask 6 (12 pts): $x_i=1$. - Subtask 7 (10 pts): the difference between each modification and the original number is at most $1$. - Subtask 8 (18 pts): no special restrictions. For $100\%$ of the data, it is guaranteed that $2\leq N\leq 5\times 10^4$, $1\leq Q\leq 10^5$, $0\leq s_i\leq 10^5$, $1\leq x_i\leq N$, $0\leq y_i\leq 10^5$. Translated by ChatGPT 5