题目描述

译自 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$，分别表示第 $j$ 名玩家从第 $S_j$ 层出发，目的地是 $T_j$，最大能量是 $U_j$。

---

输出格式

输出 $M$ 行，第 $j$ 行包含一个整数，表示玩家 $j$ 移动到 $T_j$ 的最少所需金币数。如果玩家 $j$ 不能移动到第 $T_j$ 层，输出 $-1$。

---

样例 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

因为玩家 $1$ 的最大能量是 $3$，所以玩家 $1$ 不能从第 $2$ 层移动到第 $3$ 层。所以第一行输出 $-1$。

玩家 $2$ 的最大能量是 $4$。因此玩家 $2$ 可以按下述方法移动到第 $6$ 层：

• 在第 $1$ 层，花 $8$ 个金币使自己的能量变为 $4$。然后移动到第 $2$ 层，之后他的能量变为 $1$。
• 在第 $2$ 层，花 $15$ 个金币使自己的能量变为 $4$。然后移动到第 $3$ 层，之后他的能量变为 $0$。
• 在第 $3$ 层，花 $4$ 个金币使自己的能量变为 $4$。然后移动到第 $4$ 层，之后他的能量变为 $3$。
• 在第 $4$ 层，不需要花费金币，直接移动到第 $5$ 层，之后他的能量变为 $2$。
• 在第 $5$ 层，花 $2$ 个金币使自己的能量变为 $4$。然后移动到第 $6$ 层，之后他的能量变为 $0$。

玩家 $2$ 一共花了 $29$ 个金币。因为不可能花费少于 $29$ 个金币到达第 $6$ 层，所以输出 $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

输出

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

输出

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)$。

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

子任务编号	附加限制	分值
1	$N,M\le 3\,000$	11
2	$U_1=U_2=\ldots = U_M$	14
3	$T_j=N+1$ $(1\le j\le M)$	31
4	无附加限制	44

---