프로그램 명: coci_raspored
제한시간: 2 초

[문제 요약] 피자 집에 많은 주문이 들어왔습니다. 그런데 문제가 있었는지 많은 주문이 변경되기도 했고요.

피자를 만드는 데 오븐은 하나밖에 없어 동시에 여러 작업을 할 수는 없지만 미르코의 오토바이는 메우 빠른 관계로 배달하는 데 걸리는 시간은 무시해도 됩니다. 이 피자 배달에는 특별한 점이 있는데, 원하는 시간보다 W시간만큼 더 일찍 배달하면 W만큼 팁을 받고 W시간만큼 더 늦게 배달하면 W만큼 벌금을 내야합니다.

최종적으로 우리는 주문이 조정되기 전과 주문 조정이 이루어질 때마다 미르코가 받는 팁을 최대화해 순서대로 출력해야합니다. 상황에 따라선 음수가 나와 돈을 지불해야할 수도 있습니다.

참고: 이 마을의 시간은 항상 0에서 시작합니다.

입력 크기

1번 예제 설명: 
3 2 
10 2 
6 5 
4 3 
1 6 1 
3 0 10 

주문 조정 전: 
순서: 1번->3번->2번 
시간 2에 1번 피자 완성 +8 
시간 5에 3번 피자 완성 -1 
시간 10에 2번 피자 완성 -4 
전부 더하면 3 

첫 번째 조정 
1번: 먹고 싶은 시각 6, 피자 만드는 데 걸리는 시간 1 
2번: 먹고 싶은 시각 6, 피자 만드는 데 걸리는 시간 5 
3번: 먹고 싶은 시각 4, 피자 만드는 데 걸리는 시간 3 

순서 1번->3번->2번 
시간 1에 1번 피자 완성 +5 
시간 4에 3번 피자 완성 +0 
시간 9에 2번 피자 완성 -3 
전부 더하면 2 

두 번째 조정 
1번: 먹고 싶은 시각 6, 피자 만드는 데 걸리는 시간 1 
2번: 먹고 싶은 시각 6, 피자 만드는 데 걸리는 시간 5 
3번: 먹고 싶은 시각 0, 피자 만드는 데 걸리는 시간 10 

순서: 1번->2번->3번 
시간 1에 1번 사람 피자 완성하고 +5 
시간 6에 2번 사람 피자 완성하고 +0 
시간 16에 3번사람 피자 완성하고 -16 
전부 더하면 -11 

따라서 출력은 
3 
2 
-11
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).

출력

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! :)

입출력 예

input

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

output

3
2
-11

input

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

output

-8
-13
-18

input

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

27
59
56
69
78
81
82
58

First sample description: The optimal pizza baking schedule is (1, 3, 2). That way, the first pizza will
be finished at the moment t = 2, the third one at t = 5, and the second one at t = 10. The first pizza
will be delivered 8 moments early (8 kunas tip), the second one will be 1 moment late (-1 kuna), and the
third one will be 4 moments late (-4 kunas), so the total tip is 3 kunas. When the first resident changes
requirements, the optimal schedule remains unchanged, while the tips change to 5, 0, and -3,
respectively. After the second requirement change, the optimal schedule is (1, 2, 3), while the tips are 5,
0, and -16, respectively.

Constraints:

1 <= N, C <= 200 000,
0 <= Li, L <= 100 000,
1 <= Ti, T <= 100 000,
1 <= R <= N.

출처:coci
요약:ladown21
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]