← 返回题目列表

AtCoder · joi2021ho_e

E. 地下城 3

中文机器翻译题面 查看原题

配点: 100 点

N+1 有一个由层层组成的地牢,地牢内有 有 M 名玩家。地牢楼层从入口开始按顺序排列。 1 从一层到另一层 N+1 层已编号。另外,玩家 它们的编号最大为 1 减去 M 。

从地牢的一层进入下一层需要体力。玩家 i 層 (1 \leqq i \leqq N) 至 i + 1 随着层数的推进,你的生命值会增加。 A_i 消耗。此外,这个地牢是单向的,可能楼层之间的移动仅限于第一层。 i 層 (1 \leqq i \leqq N) 至 i + 1 仅移动到该层。 直到

第 1 从一层到另一层 N 层的每一层都有 1 有两个恢复泉源。不。 在位于 i 層 (1 \leqq i \leqq N的治疗之井,玩家可以 B_i 通过消耗金币来增加你的生命值。 1 可以恢复。只要有金币,恢复之泉就可以多次使用。不过,玩家的体力是有上限的,就算使用恢复之泉,你的体力也不会超过那个上限。

玩家 j (1 \leqq j \leqq M) 目前是 我在 S_j 层。我现在的体力是 0 ,体力上限为 U_j 。玩家 j 增加体力 不少于 0 我们正在尝试前进到 T_j 层。为此需要多少硬币?

给定副本信息和每个玩家的信息,让每个玩家增加生命值。 创建一个程序,确定是否可以在不低于 0 的情况下晋级到目标级别,并且如果可能,找到所需的最小硬币数量。


入力

输入是按以下格式从标准输入给出的。所有输入值都是整数。

N M
A_1 \cdots A_N
B_1 \cdots B_N
S_1 T_1 U_1
\vdots
S_M T_M U_M

出力

到标准输出 输出为 M 行。不。 j 行目 (1 \leqq j \leqq M) 有一名玩家 j 是 T_j 打印前进到该层所需的最小硬币数量。然而,玩家 j 是 T_j 如果无法前进到该层 输出 -1 。


制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq M \leqq 200\,000.
  • 1 \leqq A_i \leqq 200\,000 (1 \leqq i \leqq N).
  • 1 \leqq B_i \leqq 200\,000 (1 \leqq i \leqq N).
  • 1 \leqq S_j < T_j \leqq N+1 (1 \leqq j \leqq M).
  • 1 \leqq U_j \leqq 100\,000\,000 (1 \leqq j \leqq M).

小課題

  1. (11 点) N \leqq 3\,000,M \leqq 3\,000.
  2. (14 点) U_1 = U_2 = \cdots = U_M.
  3. (31 点) T_j = N+1 (1 \leqq j \leqq M).
  4. (44 点)没有额外的限制。

入力例 1

5 4
3 4 1 1 4
2 5 1 2 1
1 6 3
1 6 4
3 5 1
2 5 9

出力例 1

-1
29
3
22

玩家 1 体力有上限。 3 ,所以 2 从一层到另一层 3 无法继续图层。因此,1 行的输出是 -1 变为。

另一方面,玩家 2 体力有上限。 4 ,所以 您可以进入 6 层。

  • 第 1 分层硬币 使用 8 来增加你的健康。 4 和 2 转到图层。此时的体力是 1 变为。
  • 第 2 分层硬币 使用 15 来增加你的健康。 4 和 3 转到图层。此时的体力是 0 变为。
  • 第 3 分层硬币 使用 4 来增加你的健康。 4 和 4 转到图层。此时的体力是 3 变为。
  • 第 4 第一层不使用金币。 使用 5 转到图层。此时的体力是 2 变为。
  • 第 5 分层硬币 使用 2 来增加你的健康。 4 和 6 转到图层。此时的体力是 0 变为。

合計 29 硬币。 硬币少于29 由于无法前进到 6 层,2 行的输出是 29 变为。


入力例 2

10 10
1 8 9 8 1 5 7 10 6 6
10 10 2 8 10 3 9 8 3 7
2 11 28
5 11 28
7 11 28
1 11 18
3 11 18
8 11 18
4 11 11
6 11 11
10 11 11
9 11 5

出力例 2

208
112
179
248
158
116
234
162
42
-1

此输入示例是一个小作业。 它满足 3 约束。


入力例 3

20 20
2 3 2 11 4 6 9 15 17 14 8 17 3 12 20 4 19 8 4 5
19 3 18 2 13 7 5 19 10 1 12 8 1 15 20 1 13 2 18 6
12 15 67
7 15 18
16 17 14
9 21 97
1 19 43
3 18 31
16 20 70
7 20 28
1 16 61
3 5 69
9 10 15
2 13 134
11 19 23
16 20 14
5 21 16
15 20 11
7 11 54
7 16 16
13 17 10
3 15 135

出力例 3

151
591
4
284
339
517
35
581
254
58
-1
178
519
-1
-1
-1
219
-1
-1
214