시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 2 2 2 100.000%

문제

There are $N$ mines on the number line. Mine $i$ is at position $p_i$ and has an explosion radius $r_i$. It initially costs $c_i$ to detonate. If mine $i$ is detonated, an explosion occurs on interval $[p_i - r_i, p_i + r_i]$ and all mines in that interval (inclusive of the endpoints) are detonated for free, setting off a chain reaction. You need to process $Q$ operations of the form $(m,c)$: Change the cost of detonating mine $m$ to $c$. Output the minimum cost required to detonate all mines after each change. Note that each change is permanent.

입력

The first line contains integers $N$ and $Q$ ($1 \leq N, Q \leq 200\,000$). The next $N$ lines contain information on the mines. The $i$-th of these lines contains integers $p_i$, $r_i$ and $c_i$ ($1 \leq p_i,r_i,c_i \leq 10^9$). The next $Q$ lines each contains space separated integers $m$ and $c$ ($1 \leq m \leq N$, $1 \leq c \leq 10^9$). 

출력

Output $Q$ lines. The $i$-th line should contain the minimum cost required to detonate all mines after the $i$-th operation.

예제 입력 1

4 2
1 1 1
6 3 10
8 2 5
10 2 3
1 1
4 11

예제 출력 1

4
6