P7408 [JOI 2021 Final] ダンジョン 3 (Dungeon 3)

有一栋层数为 $N+1$ 层的楼，这 $N+1$ 层编号为 $1 \sim N+1$。有 $M$ 个人，这 $M$ 个人编号为 $1 \sim M$。从第 $i$ 层移动到第 $i+1$ 层需要 $A_i$ 的能量值，并且你只能从第 $i$ 层移动到第 $i+1$ 层，不能反过来。 第 $1$ 层到第 $N$ 层都有一个商铺，第 $i$ 层的商铺可以从 $B_i$ 元使自己的能量加 $1$，可以多次使用商铺但是不能使得能量多于能量上限，其中第 $j$ 个玩家的能量上限为 $U_j$，每个人的初始能量均为 $0$。 第 $j$ 个人最开始在第 $S_j$ 层，他们要到达第 $T_j$ 层。 请回答每个人达到他们的目的地最少需要多少金币，或者指出无解。

无

无

#### 样例 1 解释 第 $1$ 个人无法到达第 $3$ 层。 第 $2$ 个人可以用如下方法到达第 $6$ 层： - 第 $1$ 层用 $8$ 个金币让自己的能量值变为 $4$。 - 移动到第 $2$ 层能量变为 $1$。 - 第 $2$ 层用 $15$ 个金币让自己的能量值变为 $4$。 - 移动到第 $3$ 层能量变为 $0$。 - 第 $3$ 层用 $4$ 个金币让自己的能量值变为 $4$。 - 移动到第 $4$ 层能量为 $3$。 - 移动到第 $5$ 层能量为 $2$。 - 第 $5$ 层用 $2$ 个金币让自己的能量值变为 $4$。 - 移动到第 $6$ 层。 一共需要 $29$ 个金币。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（11 pts）：$N,M \le 3000$。 - Subtask 2（14 pts）：$U_j$ 互相相等。 - Subtask 3（31 pts）：$T_j=N+1$。 - Subtask 4（44 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le N,M,A_i,B_i \le 2 \times 10^5$，$1 \le S_j