P10224 [COCI 2023/2024 #3] Vrsar

**译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T2「[Vrsar](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**

Vrsar 是一个由 $n$ 座小山丘组成的海滨小镇。惊人地，从海岸看去，$n$ 座山丘排成一列，第 $i$ 座山丘到海岸的距离为 $x_i$ 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天同时开放，但它们的关闭时间是不同的。第 $i$ 座溜冰场开放 $t_i$ 分钟。 Iva 和 Mia 已经来到了 Vrsar，他们将在这里停留 $m$ 天。Iva 和 Mia 热爱溜冰，他们希望在 Vrsar 停留的每一天都以溜冰度过。在第 $i$ 天的开始，他们距离海岸 $a_i$ 米。当滑雪场开放的同时，他们开始他们的溜冰之旅。他们需要走去滑雪场，走路的速度为每分钟 $1$ 米。 他们的身体非常好，因此他们不需要额外时间来爬山。一旦他们到达山顶的滑雪场，他们可以滑任意长的时间，直到滑雪场关闭。然而，下山并不像上山一样容易，因为下雨，山路非常湿滑，他们需要消耗 $s_i$ 的时间走下第 $i$ 座山。从一座山上下来后，他们可以前往另一座山。 Iva 和 Mia 想知道每天他们最长可以滑多久的雪。每天他们可以访问任意多座滑雪场。因为他们想用尽可能多的时间滑雪，用尽可能少的时间计算，所以他们向你寻求帮助。帮助他们解决这个问题。 请注意：如果 Iva 和 Mia 早晨出发的位置就有一座山，他们在山脚。

第一行包含两个整数 $n,m$（$1 \le n,m \le 10^5$），表示山的数量和天数。 接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,t_i,s_i$（$0 \le x_i,t_i,s_i \le 10^9$），分别表示第 $i$ 座山到海岸的距离、滑雪场的关闭时间和下山所需的时间。 第三行包含 $m$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示 Iva 和 Mia 第 $i$ 天出发时到海岸的距离。

输出一行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 天 Iva 和 Mia 可以滑雪的最长时间。

### 样例解释 1  Iva 和 Mia 在位置 $1$ 出发，走 $2$ 分钟到位置 $3$ 的山，并滑雪 $5$ 分钟。接着花费 $0$ 分钟时间下山，继续走 $3$ 分钟时间到位置 $6$ 山上的滑雪场，滑雪 $1$ 分钟。 他们一共滑雪 $6$ 分钟。 ### 子任务 | Subtask | Points | Constraints | | :--: | :--: | :--: | | 1 | 8 | $n,m \le 10$ | | 2 | 17 | $m=1,a_1=0$ | | 3 | 19 | $n,m \le 1000$ | | 4 | 26 | 无特殊限制。|