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.