配点: 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).
小課題
- (11 点) N \leqq 3\,000,M \leqq 3\,000.
- (14 点) U_1 = U_2 = \cdots = U_M.
- (31 点) T_j = N+1 (1 \leqq j \leqq M).
- (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