{"problem":{"name":"[COCI 2023/2024 #3] Vrsar","description":{"content":"Vrsar 是一个由 $n$ 座小山丘组成的海滨小镇。惊人地，从海岸看去，$n$ 座山丘排成一列，第 $i$ 座山丘到海岸的距离为 $x_i$ 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天同时开放，但它们的关闭时间是不同的。第 $i$ 座溜冰场开放 $t_i$ 分钟。 Iva 和 Mia 已经来到了 Vrsar，他们将在这里停留 $m$ 天。Iva 和 Mia 热爱溜冰，他们希望在 Vrsa","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10224"},"statements":[{"statement_type":"Markdown","content":"Vrsar 是一个由 $n$ 座小山丘组成的海滨小镇。惊人地，从海岸看去，$n$ 座山丘排成一列，第 $i$ 座山丘到海岸的距离为 $x_i$ 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天同时开放，但它们的关闭时间是不同的。第 $i$ 座溜冰场开放 $t_i$ 分钟。\n\nIva 和 Mia 已经来到了 Vrsar，他们将在这里停留 $m$ 天。Iva 和 Mia 热爱溜冰，他们希望在 Vrsar 停留的每一天都以溜冰度过。在第 $i$ 天的开始，他们距离海岸 $a_i$ 米。当滑雪场开放的同时，他们开始他们的溜冰之旅。他们需要走去滑雪场，走路的速度为每分钟 $1$ 米。\n\n他们的身体非常好，因此他们不需要额外时间来爬山。一旦他们到达山顶的滑雪场，他们可以滑任意长的时间，直到滑雪场关闭。然而，下山并不像上山一样容易，因为下雨，山路非常湿滑，他们需要消耗 $s_i$ 的时间走下第 $i$ 座山。从一座山上下来后，他们可以前往另一座山。\n\nIva 和 Mia 想知道每天他们最长可以滑多久的雪。每天他们可以访问任意多座滑雪场。因为他们想用尽可能多的时间滑雪，用尽可能少的时间计算，所以他们向你寻求帮助。帮助他们解决这个问题。\n\n请注意：如果 Iva 和 Mia 早晨出发的位置就有一座山，他们在山脚。\n\n## Input\n\n第一行包含两个整数 $n,m$（$1 \\le n,m \\le 10^5$），表示山的数量和天数。\n\n接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,t_i,s_i$（$0 \\le x_i,t_i,s_i \\le 10^9$），分别表示第 $i$ 座山到海岸的距离、滑雪场的关闭时间和下山所需的时间。\n\n第三行包含 $m$ 个整数 $a_i$（$1 \\le a_i \\le 10^9$），表示 Iva 和 Mia 第 $i$ 天出发时到海岸的距离。\n\n## Output\n\n输出一行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 天 Iva 和 Mia 可以滑雪的最长时间。\n\n[samples]\n\n## Background\n\n**译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T2「[Vrsar](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」**\n\n## Note\n\n### 样例解释 1\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/swsv3bec.png)\n\nIva 和 Mia 在位置 $1$ 出发，走 $2$ 分钟到位置 $3$ 的山，并滑雪 $5$ 分钟。接着花费 $0$ 分钟时间下山，继续走 $3$ 分钟时间到位置 $6$ 山上的滑雪场，滑雪 $1$ 分钟。\n\n他们一共滑雪 $6$ 分钟。\n\n### 子任务\n\n| Subtask | Points | Constraints |\n| :--: | :--: | :--: |\n| 1 | 8 | $n,m \\le 10$ |\n| 2 | 17 | $m=1,a_1=0$ |\n| 3 | 19 | $n,m \\le 1000$ |\n| 4 |  26 | 无特殊限制。|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10224","tags":["2023","COCI（克罗地亚）"],"sample_group":[["3 1\n3 7 0\n6 11 3\n10 13 5\n1","6"],["3 2\n5 10 3\n3 6 1\n1 5 0\n0 3","5 8"],["1 3\n3 3 3\n0 1 2","0 1 2"]],"created_at":"2026-03-03 11:09:25"}}