Problem Description

There is a dungeon consisting of $ N+1 $ layers, and there are $ M $ players in the dungeon. The layers of the dungeon are numbered from the 1st layer to the $ N+1 $th layer in order from the entrance. The players are numbered from 1 to $ M $.

To move from one layer to the next in the dungeon requires stamina. Players consume $ A_i $ stamina to move from the $ i $th layer ($1 \leq i \leq N$) to the $ i+1 $th layer. The dungeon is one-way, and the only possible movement between layers is from the $ i $th layer ($1 \leq i \leq N$) to the $ i+1 $th layer.

Each layer from the 1st to the $ N $th layer has one healing spring. At the healing spring on the $ i $th layer ($1 \leq i \leq N$), a player can restore 1 stamina by consuming $ B_i $ coins. The healing spring can be used as many times as coins allow, but the player's stamina has an upper limit, and using the healing spring will not exceed this limit.

Player $ j $ ($1 \leq j \leq M$) is currently on the $ S_j $th layer. Their current stamina is 0, and their stamina limit is $ U_j $. Player $ j $ is trying to reach the $ T_j $th layer without letting their stamina drop below 0. How many coins are needed for this?

Given the information about the dungeon and each player, create a program that determines whether each player can reach their target layer without letting their stamina drop below 0, and if possible, calculates the minimum number of coins required.

Input Format

The input is given from the standard input in the following format. All values are integers.

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

Output Format

Output $ M $ lines to the standard output. The $ j $th line ($1 \leq j \leq M$) should contain the minimum number of coins required for player $ j $ to reach the $ T_j $th layer. If player $ j $ cannot reach the $ T_j $th layer, output $ -1 $.

Sample Input and Output

Sample Input #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

Sample Output #1

-1
29
3
22

Sample Input #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

Sample Output #2

208
112
179
248
158
116
234
162
42
-1

Sample Input #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

Sample Output #3

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

Notes/Hints

Constraints

• $1 \leq N \leq 200,000$.
• $1 \leq M \leq 200,000$.
• $1 \leq A_i \leq 200,000$ ($1 \leq i \leq N$).
• $1 \leq B_i \leq 200,000$ ($1 \leq i \leq N$).
• $1 \leq S_j < T_j \leq N+1$ ($1 \leq j \leq M$).
• $1 \leq U_j \leq 100,000,000$ ($1 \leq j \leq M$).

Subtasks

1. ($ 11 $ points) $N \leq 3,000$, $M \leq 3,000$.
2. ($ 14 $ points) $U_1 = U_2 = \cdots = U_M$.
3. ($ 31 $ points) $ T_j = N+1 $ ($1 \leq j \leq M$).
4. ($ 44 $ points) No additional constraints.

Sample Explanation 1

Player $ 1 $ cannot move from the 2nd layer to the 3rd layer because their stamina limit is $ 3 $. Therefore, the output for the 1st line is $ -1 $. On the other hand, player $ 2 $ can reach the 6th layer as follows:
- Use $ 8 $ coins at the 1st layer to restore stamina to $ 4 $ and move to the 2nd layer, leaving stamina at $ 1 $.
- Use $ 15 $ coins at the 2nd layer to restore stamina to $ 4 $ and move to the 3rd layer, leaving stamina at $ 0 $.
- Use $ 4 $ coins at the 3rd layer to restore stamina to $ 4 $ and move to the 4th layer, leaving stamina at $ 3 $.
- Move to the 5th layer without using coins, leaving stamina at $ 2 $.
- Use $ 2 $ coins at the 5th layer to restore stamina to $ 4 $ and move to the 6th layer, leaving stamina at $ 0 $.

A total of $ 29 $ coins are used. Since fewer than $ 29 $ coins cannot reach the 6th layer, the output for the 2nd line is $ 29 $.

Sample Explanation 2

This input example satisfies the constraints of subtask $ 3 $.

见题面 Input 部分

见题面 Output 部分