题目描述

有一栋层数为 $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$ 层。

请回答每个人达到他们的目的地最少需要多少金币，或者指出无解。

输入格式

第一行两个整数 $N,M$ 代表楼的层数和人数。

第二行 $N$ 个整数 $A_i$ 代表移动需要的能量值。

第三行 $N$ 个整数 $B_i$ 代表每一层的商铺购买能量需要的金币数。

接下来 $M$ 行每行三个整数 $S_j,T_j,U_j$ 描述一个人。

输出格式

$M$ 行每行一个整数代表第 $j$ 个人要到第 $T_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 解释

第 $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<T_j \le N+1$，$1 \le U_j \le 10^9$。

说明

翻译自 The 20th Japanese Olympiad in Informatics Final Round E ダンジョン 3 的英文翻译 Dungeon 3。