题目描述

Mirko 的比萨店是城里最好的，镇上所有的居民每天午餐都吃比萨饼。而且 Mirko 的送货服务很快，送货时间可以忽略不计。但是 Mirko 只有一个小烤箱，一次只能烤一个比萨饼。

我们将城里的 $N$ 个居民从 $1$ 到 $N$ 编号，他们计划吃午餐的时间为 $L_i$，Mirko 需要为他们烘焙比萨的所需时间为 $T_i$。

如果一个居民在他计划吃午餐时间的前 $K$ 个时间单位收到了他的比萨饼，那么 Mirko 会得到 $K$ 元小费。相应地，如果一个居民在他计划吃午餐时间的后 $K$ 个时间单位才收到了他的比萨饼，那么 Mirko 必须向居民付款 $K$ 元。如果比萨饼准时送到，Mirko 不会得到小费，但是也不用付任何费用。

请你帮助 Mirko 安排一天的比萨烘焙顺序，使得他一天赚取的总小费最大。

注意：

1. 一天从时间单位 $0$ 开始，你可以认为这一天是无限长的。

2. 居民们有时会改变他们的 $T_i,L_i$。

输入格式

输入的第一行包含两个正整数 $N,C$，分别表示居民人数和比萨需求改变的数量。

接下来 $N$ 行，每行包含两个整数 $L_i,T_i$。

接下来 $C$ 行，每行包含三个正整数 $R_j,L_j,T_j$，分别表示要改变的居民编号、改变后的 $L_i$ 和改变后的 $T_i$。

输出格式

输出的第一行包含一个整数，表示未修改前 Mirko 能得到的最大总小费。

接下来对于每一个修改操作输出一行一个整数，表示这次修改后 Mirko 能得到的最大总小费。

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

提示

【样例 1 解释】

最优的比萨烘焙顺序为 $(1,3,2)$。这样的话，第 $1$ 个比萨在第 $2$ 个时间单位送达，第 $3$ 个比萨在第 $5$ 个时间单位送达，第 $2$ 个比萨在第 $10$ 个时间单位送达。

第 $1$ 个比萨由于早送了 $8$ 个时间单位，所以 Mirko 得到了 $8$ 元小费；第 $2$ 个比萨由于迟送了 $1$ 个时间单位，所以 Mirko 需要付 $1$ 元；第 $3$ 个比萨由于迟送了 $4$ 个时间单位，所以 Mirko 需要付 $1$ 元。因此最大的总小费为 $3$。

经过第 $1$ 次修改后，比萨烘焙顺序没有变，小费变成了 $5,0,-3$。

经过第 $2$ 次修改后，比萨烘焙顺序变为 $(1,2,3)$，小费变成了 $5,0,-11$。

【数据范围】

对于 $50\%$ 的数据，$1 \le T_i,T_j \le 10^3$。

对于 $100\%$ 的数据，$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$。

【说明】

本题分值按 COCI 原题设置，满分 $150$。

题目译自 COCI2011-2012 CONTEST #2 T6 RASPORED。