Description

Mirko’s pizza shop is the best in town, and all residents eat pizza for lunch every day. Also, Mirko’s delivery service is very fast, so the delivery time can be ignored. However, Mirko has only one small oven, and he can bake only one pizza at a time.

We number the $N$ residents in the town from $1$ to $N$. The time when resident $i$ plans to eat lunch is $L_i$, and the time Mirko needs to bake their pizza is $T_i$.

If a resident receives their pizza $K$ time units before their planned lunch time, Mirko gets a tip of $K$ dollars. Similarly, if a resident receives their pizza $K$ time units after their planned lunch time, Mirko must pay the resident $K$ dollars. If the pizza is delivered exactly on time, Mirko gets no tip and pays nothing.

Please help Mirko arrange the baking order for the day so that the total tip (profit) for the day is maximized.

Notes:

1. The day starts at time unit $0$, and you may assume the day is infinitely long.

2. Residents sometimes change their $T_i, L_i$.

Input Format

The first line contains two positive integers $N, C$, representing the number of residents and the number of pizza-demand changes.

The next $N$ lines each contain two integers $L_i, T_i$.

The next $C$ lines each contain three positive integers $R_j, L_j, T_j$, representing the index of the resident to change, the new $L_i$, and the new $T_i$.

Output Format

The first line contains one integer, the maximum total tip Mirko can get before any modifications.

Then, for each modification, output one line with one integer, the maximum total tip after this modification.

3 2
10 2
6 5
4 3
1 6 1
3 0 10

3
2
-11

4 2
3 2
0 3
4 3
4 1
3 0 4
1 4 5

-8
-13
-18

6 7
17 5
26 4
5 5
12 4
8 1
18 2
3 31 3
4 11 5
4 19 3
5 23 2
6 15 1
5 19 1
3 10 4

27
59
56
69
78
81
82
58

Hint

Sample 1 Explanation

The optimal baking order is $(1,3,2)$. Then, pizza $1$ is delivered at time unit $2$, pizza $3$ is delivered at time unit $5$, and pizza $2$ is delivered at time unit $10$.

Pizza $1$ is delivered $8$ time units early, so Mirko gets a tip of $8$ dollars; pizza $2$ is delivered $1$ time unit late, so Mirko must pay $1$ dollar; pizza $3$ is delivered $4$ time units late, so Mirko must pay $4$ dollars. Therefore, the maximum total tip is $3$.

After the first modification, the baking order does not change, and the tips become $5,0,-3$.

After the second modification, the baking order becomes $(1,2,3)$, and the tips become $5,0,-16$.

Constraints

For $50\%$ of the testdata, $1 \le T_i, T_j \le 10^3$.

For $100\%$ of the testdata, $1 \le N, C \le 2 \times 10^5$, $0 \le L_i, L_j \le 10^5$, $1 \le T_i, T_j \le 10^5$, $1 \le R_j \le N$.

Notes

The score for this problem follows the original COCI settings, with a full score of $150$.

Translated from COCI2011-2012 CONTEST #2 T6 RASPORED.

Translated by ChatGPT 5