Problem Description

There is a building with $N+1$ floors, numbered from $1$ to $N+1$. There are $M$ people, numbered from $1$ to $M$. Moving from the $i$-th floor to the $(i+1)$-th floor requires $A_i$ energy units, and you can only move from the $i$-th floor to the $(i+1)$-th floor, not in the opposite direction.

Each floor from the 1st to the $N$-th has a shop. The shop on the $i$-th floor can increase your energy by 1 unit for $B_i$ coins. You can use the shop multiple times but cannot exceed the energy limit. The energy limit for the $j$-th player is $U_j$, and everyone starts with 0 energy.

The $j$-th person starts on the $S_j$-th floor and needs to reach the $T_j$-th floor.

Determine the minimum number of coins each person needs to reach their destination, or indicate if it is impossible.

Input Format

The first line contains two integers $N$ and $M$, representing the number of floors and the number of people, respectively.

The second line contains $N$ integers $A_i$, representing the energy required to move between floors.

The third line contains $N$ integers $B_i$, representing the cost in coins to increase energy by 1 unit at each floor's shop.

The next $M$ lines each contain three integers $S_j$, $T_j$, and $U_j$, describing a person's starting floor, target floor, and energy limit.

Output Format

Output $M$ lines, each containing a single integer representing the minimum number of coins the $j$-th person needs to reach the $T_j$-th floor.

If it is impossible for the $j$-th person to reach the $T_j$-th floor, output $-1$.

Sample Input and Output

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

Output Sample #1

-1
29
3
22

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

Output Sample #2

208
112
179
248
158
116
234
162
42
-1

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

Output Sample #3

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

Notes/Hints

Sample 1 Explanation

The first person cannot reach the 3rd floor.

The second person can reach the 6th floor using the following method:

• Use 8 coins on the 1st floor to increase energy to 4.
• Move to the 2nd floor, energy becomes 1.
• Use 15 coins on the 2nd floor to increase energy to 4.
• Move to the 3rd floor, energy becomes 0.
• Use 4 coins on the 3rd floor to increase energy to 4.
• Move to the 4th floor, energy is 3.
• Move to the 5th floor, energy is 2.
• Use 2 coins on the 5th floor to increase energy to 4.
• Move to the 6th floor.

This requires a total of 29 coins.

Data Constraints

This problem uses batched testing.

• Subtask 1 (11 pts): $N, M \le 3000$.
• Subtask 2 (14 pts): $U_j$ are all equal.
• Subtask 3 (31 pts): $T_j = N+1$.
• Subtask 4 (44 pts): No additional constraints.

For $100\%$ of the data, $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$.

见题面 Input 部分

见题面 Output 部分