Maximizing Milk Production

Farmer John has N cows, each producing milk at an integer rate. The i^th cow produces \(a_i\) units of milk per minute. Every morning, all cows are initially hooked up to the milking machine. Farmer John then unhooks the cows one by one. The first cow is unhooked after 1 minute, the second after 2 minutes (i.e. 1 additional minute), the third after 3 minutes, and so on. Consequently, the first cow contributes \(a_x\) units, the second \(2a_y\) units, the third \(3a_z\) units, etc.

By choosing an optimal order to unhook the cows, Farmer John can maximize the total milk collected. Let \(T\) denote this maximum total, which can be computed by ordering the cows such that the cow with the smallest milk production is unhooked first, the next smallest second, and so on. In other words, if \(s_1, s_2, \dots, s_N\) is the sorted list of milk production values in increasing order, then:

[ T = \sum_{i=1}^{N} i \cdot s_i. ]

Farmer John is curious about how this maximum total \(T\) would change if some milk production values were different. You are given Q queries. Each query consists of two integers \(i\) and \(j\) and asks: if the milk production value \(a_i\) were temporarily changed to \(j\), what would be the new value of \(T\)? Note that each query is independent, meaning that after each query, \(a_i\) reverts back to its original value.

Note: The time limit for this problem is 4 seconds (twice the default).

inputFormat

The first line contains two integers N and Q indicating the number of cows and the number of queries, respectively. The second line consists of N integers \(a_1, a_2, \dots, a_N\) representing the milk production values. Each of the next Q lines contains two integers \(i\) and \(j\) representing a query where the value of \(a_i\) is temporarily set to \(j\).

outputFormat

For each query, output a single line containing the maximum total milk \(T\) that can be collected after the temporary change.

sample

3 3
3 1 2
1 2
2 4
3 0

11
20
11