AT_joi2021ho_e.ダンジョン 3 (Dungeon 3)

在一个 $N+1$ 层的地下城中，有 $M$ 名玩家。地下城的层数从入口开始依次编号为第 $1$ 层到第 $N+1$ 层。玩家编号从 $1$ 到 $M$。

要从地下城的某层移动到下一层，需要消耗一定的体力。玩家从第 $i$ 层（$1 \leq i \leq N$）移动到第 $i+1$ 层时，会消耗 $A_i$ 的体力。此外，地下城是单向通行的，只能从第 $i$ 层向第 $i+1$ 层移动。

从第 $1$ 层到第 $N$ 层的每一层都有一座恢复之泉。在第 $i$ 层（$1 \leq i \leq N$）的恢复之泉中，玩家可以花费 $B_i$ 枚金币来恢复 $1$ 点体力。只要金币足够，恢复之泉可以反复使用。但玩家的体力有上限，即使使用恢复之泉，体力也不会超过这个上限。

每位玩家 $j$（$1 \leq j \leq M$）目前位于第 $S_j$ 层，当前体力为 $0$，体力上限为 $U_j$。玩家 $j$ 想要在不让体力变为负值的情况下到达第 $T_j$ 层。为此，他需要多少枚金币？

根据提供的地下城和每个玩家的信息，请编写一个程序，判断每个玩家是否可以在体力不为负的情况下到达目标层，并在可能的情况下计算所需的最小金币数。

输入数据从标准输入中给出，格式如下。所有输入的值均为整数。

$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$，输出他到达第 $T_j$ 层所需的最少金币数。如果某玩家无法到达第 $T_j$ 层，则输出 -1。

约束条件

• $1 \leq N \leq 200\,000$
• $1 \leq M \leq 200\,000$
• $1 \leq A_i \leq 200\,000$
• $1 \leq B_i \leq 200\,000$
• $1 \leq S_j < T_j \leq N+1$
• $1 \leq U_j \leq 100\,000\,000$

子任务

1. （11 分）$N \leq 3\,000$，$M \leq 3\,000$
2. （14 分）$U_1 = U_2 = \cdots = U_M$
3. （31 分）$T_j = N+1$
4. （44 分）没有额外的约束。

示例解释 1

对于玩家 $1$，由于体力上限为 $3$，他无法从第 $2$ 层移动到第 $3$ 层，故输出 -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$ 枚金币，用更少的金币无法到达第 $6$ 层，因此第二行输出为 29。

示例解释 2

此输入示例满足子任务 3 的约束条件。

本翻译由 AI 自动生成