Problem Description

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:

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.

Input Format

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 Format

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

4 2
2 0 2 3
2 4
4 0

10
14
12

Hint

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