현주의 피자 가게

현주는 피자 가게를 운영한다. 가게에는 오븐이 하나뿐이라 한 번에 피자 한 판만 구울 수 있다. 배달 시간은 0에 가깝다고 보고 무시한다.

사람은 총 N명이며 1번부터 N번까지 번호가 붙어 있다. i번 사람이 원하는 점심 시간은 L_i, 그 사람이 원하는 피자를 굽는 데 걸리는 시간은 T_i이다. 피자가 원하는 시간보다 K분 빨리 도착하면 배달원은 K원의 팁을 받고, K분 늦게 도착하면 K원을 잃는다. 정확히 도착하면 팁 변화는 없다.

하루가 시작되기 전에 현재 주문 정보로 피자 굽는 일정을 정해야 한다. 이후 C번의 전화가 순서대로 오며, 각 전화는 한 사람의 원하는 점심 시간과 피자 굽는 시간을 새 값으로 바꾼다. 모든 전화는 피자를 굽기 시작하기 전인 시간 0에 온다고 생각한다.

처음 상태와 각 전화가 반영된 뒤의 상태마다, 배달원이 받을 수 있는 총 팁의 최댓값을 구하라. 총 팁은 음수일 수 있다.

첫째 줄에 사람 수 N과 전화 수 C가 주어진다.

다음 N개의 줄에는 i번 사람이 점심을 먹고 싶은 시간 L_i와 그 사람이 원하는 피자를 굽는 데 걸리는 시간 T_i가 주어진다.

다음 C개의 줄에는 전화가 온 순서대로 세 정수 R, L, T가 주어진다. 이는 R번 사람의 점심 시간이 L로, 피자를 굽는 데 걸리는 시간이 T로 바뀐다는 뜻이다.

첫 줄에 아무 전화도 반영하지 않은 처음 상태에서 가능한 최대 총 팁을 출력한다.

이후 C개의 줄에는 각 전화가 반영된 뒤의 상태에서 가능한 최대 총 팁을 전화 순서대로 하나씩 출력한다.

• 1 ≤ N, C ≤ 200,000
• 0 ≤ L_i, L ≤ 100,000
• 1 ≤ T_i, T ≤ 100,000
• 1 ≤ R ≤ N