19336번 - Mines 다국어

문제

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.

제한

힌트