[COCI2011-2012#2] RASPORED

题目描述

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 能得到的最大总小费。

输入输出样例

输入样例 #1

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

输出样例 #1

3
2
-11

输入样例 #2

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

输出样例 #2

-8
-13
-18

输入样例 #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

输出样例 #3

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](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #2](https://hsin.hr/coci/archive/2011_2012/contest2_tasks.pdf)** ___T6 RASPORED___。