溜冰场

题目描述:

冰川镇是一个由 $n$ 座小山丘组成的海滨小镇。惊人地，从海岸看去，  $n$ 座山丘排成一行，第 $i( 1 \le i \le n ) $ 座山丘到海岸的距离为 $x_i$ 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天都同时开放，但它们的关闭时间是不同的。第 $i( 1 \le i \le n ) $个溜冰场开放到第 $t_i$ 分钟。

狐狸尼克和兔警官朱迪已经来到了冰川镇，他们将在这里停留 $m$天。尼克和朱迪都热爱溜冰，他们希望在冰川镇停留的每一天都以溜冰度过。在第 $j( 1 \le i \le m ) $  天的开始，他们距离海岸 $a_j$ 米。当溜冰场开放的同时，他们开始了他们的溜冰之旅。他们需要走去溜冰场，走路的速度为每分钟$1$米。

当他们到达山脚时，可以乘坐缆车到达山顶（并不需要耗时）。一旦他们到达山顶的溜冰场，他们可以滑任意长的时间，直到溜冰场关闭。然而，由于经费的原因下山并没有缆车，只能步行。再加上天气的原因，山路非常湿滑，他们需要消耗 $s_i$ 的时间走下第 $i( 1 \le i \le n ) $ 座山。从一座山上下来后，他们可以前往另一座山。

尼克和朱迪想知道每天他们最长可以溜冰多长时间。每天他们可以访问任意多个溜冰场，因为他们想用尽可能多的时间溜冰。请你来帮助他们解决这个问题。

请注意：如果尼克和朱迪早晨出发的位置就有一座山，那么他们在山脚。

输入格式:

第一行包含两个整数$n,m$，表示山丘的数量和他们在冰川镇停留的天数。

接下来$n$行，第 $i( 1 \le i \le n ) $ 行包含三个整数 $x_i, t_i, s_i$，分别表示第$i$座山到海岸的距离、溜冰场的关闭时间和尼克他们下山所需的时间。

再接下来一行包含$m$个整数 $a_1,a_2,\dots, a_m$，其中  $j( 1 \le i \le m ) $  表示尼克和朱迪第$j$天出发时到海岸的距离。

输出格式:

输出共一行 $m$个整数，第$j( 1 \le i \le m ) $个整数表示第 $j$天尼克和朱迪可以溜冰的最长时间。

测试点编号	特殊限制
1~4	$ 1 \le n,m \le 10$
5~8	$m=1； a_1 = 0 $
9~14	$1 \le n,m \le 1000$
15~20	无特殊限制

数据范围:

对于100%的数据： $ 1 \le n,m \le 100,000；0 \le x_i, t_i,s_i \le 10^9( 1 \le i \le n )；0 \le a_j \le 10^9 ( 1 \le j \le m )$。

样例输入:

(双击复制)

样例1：
3 1
3 7 0
6 11 3
10 13 5
1

样例2：
3 2
5 10 3
3 6 1
1 5 0
0 3

样例3：
1 3
3 3 3
0 1 2

样例输出:

(双击复制)

样例1：
6

样例2：
5 8

样例3：
0 1 2

提示:

尼克和朱迪从位置$1$ 出发，走$2$ 分钟到位置$3$ 的山，并溜冰$5$ 分钟。接着花费$0$ 分钟时间下山，继续走$3$ 分钟时间到位置$6$ 的山上的溜冰场，溜冰$1$ 分钟。他们一共溜冰 $5+1=6$ 分钟。

时间限制: 1000ms
空间限制: 256MB

---

来源: 26年比赛初中组t3