Posters

This problem is adapted from ROIR 2020 Day2 T4. (Translated by ksyx)

Your friends have prepared many beautiful posters to welcome the national team members returning from IOI. They plan to stand in a circle, numbered 1...n in clockwise order (so that for every i with 1 ≤ i ≤ n-1, friend i stands next to friend i+1, and friend n stands next to friend 1). Friend i holds a poster with aesthetic value a_i.

When the celebration starts, some friends will raise their posters. To keep a pleasing display, it is forbidden that four or more consecutive friends (in the circle) raise their posters. In other words, if we denote by 1 the friend raising his/her poster and 0 otherwise, any sequence of four consecutive ones is forbidden. In mathematical terms, for any consecutive block (wrapping around in the circle) the count of ones must be at most 3, i.e. if friends i, i+1, i+2, i+3 (indices taken modulo n) are all chosen then the configuration is invalid. Equivalently, note that in any valid configuration the following inequality must hold: $$\text{for any block, } r_1+r_2+r_3+r_4 \le 3.$$

To add some variety to the celebration, there will be q updates. In each update, the aesthetic value of poster p_i becomes q_i. Your task is to compute the maximum possible total aesthetic sum that can be obtained by selecting a set of friends to raise their posters (subject to the condition above) under the initial configuration and after each update.

Input constraints and notes: The first input line contains two integers n and q. The second line contains n integers: a₁, a₂, \dots, a_n. Then follow q lines each containing two integers p_i and q_i (1-indexed), which mean that the value at position p_i is updated to q_i. It is guaranteed that a valid selection exists.

Output: Output a total of q+1 lines. The first line should contain the maximum aesthetic sum for the initial configuration, and each of the following q lines should contain the maximum aesthetic sum after the corresponding update.

Note: In any configuration, the selection of friends must obey the rule that there are no four or more consecutive friends (taking the circle into account) all raising their posters.

## inputFormat

The first line contains two integers n and q (number of friends and number of updates).

The second line contains n integers: a₁ a₂ ... a_n, representing the aesthetic values of the posters.

Then q lines follow. Each line contains two integers p_i and q_i representing an update (the poster at position p_i gets its value changed to q_i).

## outputFormat

Output q+1 lines. The first line is the maximum total aesthetic sum for the initial configuration, and then each subsequent line corresponds to the result after each update.

## sample

3 1
1 2 3
2 10

6
14

$$