문제

Author: Gustav Matula

Mirko’s pizza place is the best one in town. It is so good that all town residents eat pizza for lunch every day. Mirko’s delivery service is so fast that the delivery time is negligible. The problem is baking the pizzas, since all residents have their own favourite topping combination, so baking pizzas for two different residents doesn’t always take the same amount of time. Mirko only has one small baking oven with a capacity of a single pizza at a time, so good scheduling is extremely important and must be determined before the day starts. For each of the N town residents (denoted by numbers from 1 to N) we know the baking duration for their favourite pizza (Ti), as well as the moment in the day when they plan on having lunch (Li). If a resident receives their pizza K moments before the planned lunch time, Mirko is rewarded with a tip of K kunas1. On the other hand, if the pizza is delivered K moments late (after the planned lunch time), Mirko must pay the resident K kunas (because of his timely delivery insurance policy). If the pizza is delivered precisely on time, Mirko won’t get a tip, but he doesn’t have to pay anything either. Mirko would like to know the maximum total tip (including all insurance payouts as negative tips) that can be earned in a day if pizzas are baked in an optimal order. Notice that Mirko can earn a negative total tip (if he has to pay out more insurance than the amount of tips he receives). Since residents sometimes change their favourite pizza toppings, as well as their preferred lunch time, Mirko’s schedule must be adapted in order to keep earning optimal tip amounts. Write a program to compute the maximum total tip for the beginning requirements, as well as after each change. Note: In this town, the day starts at the moment t = 0 and lasts much longer than the time needed to bake pizzas for all residents. The schedule, including the adaptations, must be determined before the day starts.

입력

The first line of input contains two positive integers N and C, the number of residents and the number of pizza requirement changes, respectively. Each of the next N lines contains two positive integers: Li, the moment when resident i plans on having lunch, and Ti, the time needed to bake the pizza for resident i. Each of the next C lines contains three positive integers: R (the index of a resident), L (the new moment when resident R plans on having lunch), and T (the time needed to bake resident R’s new favourite pizza). Constraints: 1 ≤ N, C ≤ 200 000, 0 ≤ Li, L ≤ 100 000, 1 ≤ Ti, T ≤ 100 000, 1 ≤ R ≤ N.

출력

The first line of output must contain the maximum total tip for the beginning requirements of the residents. For each of the C changes, the output must contain an additional line of output containing the new maximum total tip value after the change.

1 Kuna - Croatian currency. 1 kuna = 100 lipa(s); 1 € = about 7.5 kuna(s). Come to Croatia! :) Author: Gustav Matula

예제 입력 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