Problem Description

Mirko's pizza shop is the best in town, and all the residents eat pizza for lunch every day. Mirko's delivery service is also very fast, with negligible delivery time. However, Mirko only has a small oven that can bake one pizza at a time.

We number the town's \( N \) residents from \( 1 \) to \( N \), with their planned lunch times being \( L_i \) and the time required for Mirko to bake their pizza being \( T_i \).

If a resident receives their pizza within \( K \) time units before their planned lunch time, Mirko earns \( K \) dollars in tips. Conversely, 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 on time, Mirko does not receive any tips but also does not have to pay anything.

Help Mirko arrange the order of pizza baking for the day to maximize his total tips.

Note:

1. The day starts at time unit \( 0 \), and you can consider the day to be infinitely long.
2. Residents may change their \( T_i, L_i \).

Input Format

The first line of input contains two positive integers \( N, C \), representing the number of residents and the number of changes in pizza demands, respectively.

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 resident number to be changed, the new \( L_i \), and the new \( T_i \), respectively.

Output Format

The first line of output contains an integer representing the maximum total tips Mirko can earn before any modifications.

For each modification, output one line containing an integer representing the maximum total tips Mirko can earn after that modification.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3
2
-11

Input Sample #2

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

Output Sample #2

-8
-13
-18

Input Sample #3

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

Output Sample #3

27
59
56
69
78
81
82
58

Notes

Sample 1 Explanation

The optimal pizza baking order is \((1, 3, 2)\). This way, the first pizza is delivered at the 2nd time unit, the third pizza at the 5th time unit, and the second pizza at the 10th time unit.

The first pizza, delivered 8 time units early, earns Mirko 8 dollars in tips; the second pizza, delivered 1 time unit late, costs Mirko 1 dollar; the third pizza, delivered 4 time units late, costs Mirko 1 dollar. Thus, the maximum total tips are 3.

After the first modification, the pizza baking order remains the same, and the tips become 5, 0, -3.

After the second modification, the pizza baking order changes to \((1, 2, 3)\), and the tips become 5, 0, -11.

Data Range

For 50% of the data, \( 1 \le T_i, T_j \le 10^3 \).

For 100% of the data, \( 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

This problem is worth 150 points, as set by the COCI.

The problem is translated from COCI2011-2012 CONTEST #2 T6 RASPORED.

见题面 Input 部分

见题面 Output 部分