시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 16 6 6 40.000%

문제

현주는 안암에서 피자가게를 하고 있다. 이 피자 가게는 환상적인 맛으로 대전에서 엄청난 인기를 끌었고, 대전에 사는 모든 사람들은 점심으로 현주네 피자가게를 이용한다. 현주네 피자가게에서 배달부로 일하는 현정이는 전국 스쿠터 배달 대회 1등 출신이다. 1등 출신 답게 그가 피자를 배달하는데 걸리는 시간은 0에 매우 가깝기 때문에 무시할 수 있다.

배달은 현정이를 통해서 해결하면 되지만, 문제는 피자를 만드는데 시간이 오래걸린다는 것이다. 사람들이 가장 좋아하는 피자의 토핑 조합은 사람마다 다르다. 또, 현주네 가게에 있는 오븐은 매우 작아서 한번에 피자 하나만 구울 수 있다. 따라서, 피자를 굽는 일정을 정하기 위해서 요즘 동혁이를 영입하였다.

동혁이는 날이 시작하기 전에 피자를 만드는 일정을 작성해야 한다.

대전에는 총 N명이 살고 있다. 현주는 모든 사람들에게 고유 번호를 붙여주었고, 번호는 1부터 N까지이다. 동혁이는 일을 시작하기 전에 미리 i가 좋아하는 피자를 만드는데 걸리는 시간(Ti)을 조사했고, 점심을 먹기 원하는 시간(Li)를 조사했다. 만약 피자를 Li보다 K분 빠른 시간에 배달한다면, 현정이는 팁으로 K원을 받게 된다. 또, K분 늦게 배달한다면, 현정이는 K원을 뺏기게 된다. 피자가 정확한 시간에 도착한다면, 팁도 받을 수 없고, 뺏기는 돈도 없다.

동혁이는 학비를 내느라 고생하는 현정이를 위해서, 현정이가 팁을 가능한 많이 받게 일정을 작성하려고 한다. 물론, 현정이가 받는 팁은 음수일 수도 있다. 이러한 경우는 피자를 늦게 배달해서 벌금으로 내는 돈이 더 많을 때이다.

그런데, 가끔 변화를 주기 위해서 좋아하는 피자를 바꾸는 사람도 있다. 이렇게 좋아하는 피자가 바뀔 때는, 원하는 점심 시간이 변할 수도 있다. 이렇게 시키려는 피자를 바꾸려면, 시간이 0일 때 현주네 피자가게로 전화를 해야 한다.

시간이 0인 시간은 피자를 굽기 시작하기 전까지 무한히 지속된다고 한다. 또, 모든 전화는 시간이 0인 동안 온다.

가장 먼저 원래 사람들이 시키려고 한 피자의 정보로 일정을 구한다. 그 다음에, 좋아하는 피자를 바꾸는 전화가 올 때 마다, 일정을 다시 구하는 프로그램을 작성하시오. 동혁이는 현정이가 받는 팁이 가장 커지게 일정을 작성해야 한다.

입력

첫째 줄에 사람의 수 N과 현주가 받은 전화의 수 C가 주어진다. (1 ≤ N,C ≤ 200,000)

둘째 줄부터 N개의 줄에는 i가 점심을 먹는 시간 Li와 그가 좋아하는 피자를 굽는데 드는 시간 Ti가 주어진다.

다음 C개 줄에는 세 정수 R(전화를 건 사람의 번호), L(R이 점심을 먹을 새로운 시간), T(R이 좋아하는 피자를 굽는데 드는 시간)이 전화가 온 순서대로 주어진다.

0 ≤ Li, L ≤ 100,000

1 ≤ Ti, T ≤ 100,000

1 ≤ R ≤ N

출력

첫째 줄에 아무 전화도 받지 않았을 때, 현정이가 받게되는 최대 팁을 출력한다.

다음 줄부터 C개 줄에는, 각 전화에 의해서 변경되는 일정에서 현정이가 받게되는 최대 팁을 출력한다.

예제 입력

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

예제 출력

3
2
-11

힌트