题目描述

译自 JOI 2021 Final T5「ダンジョン 3 / Dungeon 3」

有一个 $N+1$ 层的地牢，在地牢里有 $M$ 个玩家。地牢的每层从入口开始，用 $1$ 到 $N+1$ 的整数编号。玩家从 $1$ 到 $M$ 标号。

玩家使用能量从一层移动到下一层。玩家从第 $i\ (1\le i\le N)$ 层移动到第 $i+1$ 层所用的能量为 $A_i$。因为这是一个单向通行的地牢，所以玩家只能从第 $i$ 层移动到第 $i+1$ 层，并且要保证 $1\le i\le N$。

在第 $1$ 到第 $N$ 层的每层（包括第 $1$ 和第 $N$ 层）都有治疗泉。在第 $i$ 层的治疗泉处，玩家可以花 $B_i$ 金币，使自己的能量增加 $1$。只要玩家有足够的金币，他就可以多次使用治疗泉。但是，每个玩家都有最大能量，使用治疗泉的话也不能使自己的能量超过最大值。

现在玩家 $j\ (1\le j\le M)$ 在第 $S_j$ 层。他目前的能量为 $0$。他的最大能量是 $U_j$。他想要到第 $T_j$ 层。在路上他的能量不能小于 $0$。他需要多少金币呢？

给定这个地牢和玩家的信息，写一个程序计算对于每个玩家，是否可以在移动过程中能量不小于 $0$ 的情况下到达目的地。如果可以的话，计算他最少需要多少金币才能达成目标。

输入格式

第一行两个整数 $N,M$；

第二行 $N$ 个整数 $A_i$；

第三行 $N$ 个整数 $B_i$；

接下来 $M$ 行，每行三个整数 $S_j,T_j,U_j$，分别表示第 $i$ 名玩家从第 $S_i$ 层出发，目的地是 $T_j$，最大能量是 $U_j$。

输出格式

输出 $M$ 行，第 $j$ 行包含一个整数，表示玩家 $j$ 移动到 $T_j$ 的最少所需金币数。如果玩家 $j$ 不能移动到第 $T_j$ 层，输出 $-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
29
3
22

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

208
112
179
248
158
116
234
162
42
-1

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

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

数据范围与提示

对于所有数据，满足：

• $1\le N,M\le 2\times 10^5$；
• $1\le A_i,B_i\le 2\times 10^5\ (1\le i\le N)$；
• $1\le S_j<T_j\le N+1\ (1\le j\le M)$；
• $1\le U_j\le 10^8\ (1\le j\le M)$。

详细子任务附加限制及分值如下表：