You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $N$ 颗炸弹排列在一条线上，第 $i$ 颗炸弹在位置 $p_{i}$ 处，爆炸半径为 $r_{i}$，人工引爆所需要的花费为 $c_{i}$。

当第 $i$ 颗炸弹被引爆后，会自动引爆 $[p_{i} - r_{i}, p_{i} + r_{i}]$ 范围内的炸弹，然后传递下去。

现在给出 $Q$ 次询问，每次询问将第 $x$ 颗炸弹的人工引爆花费更改为 $c$ 后，引爆所有炸弹所需要的最小花费。

询问的更改操作是持久化的（对后面所有的询问生效）。

输入输出格式

输入格式

第一行有两个整数 $N, Q$。

接下来 $N$ 行，每行有三个整数，表示每颗炸弹的 $p_{i}$，$r_{i}$ 和 $c_{i}$。

接下来 $Q$ 行，每行有两个整数，表示每次询问的 $x$ 与 $c$。

输出格式

对于每次询问输出一行，每行一个整数，表示最小花费。

输入输出样例

|输入样例#1:

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

输出样例#1:

4 
6

说明

对于20%的数据：$1 \leq N, Q \leq 20$；

对于60%的数据：$1 \leq N, Q \leq 1000$；

对于100%的数据：$1 \leq N \leq Q \leq 2 \times 10^5$，$1 \leq p_{i}, r_{i}, c_{i} \leq 10^9$，$1 \leq x \leq N$，$1 \leq c \leq 10^9$。