Description

There is a building with $N+1$ floors, numbered $1 \sim N+1$. There are $M$ people, numbered $1 \sim M$. Moving from floor $i$ to floor $i+1$ costs $A_i$ energy, and you can only move from floor $i$ to floor $i+1$, not the other way around.

From floor $1$ to floor $N$, there is a shop on each floor. At the shop on floor $i$, you can pay $B_i$ coins to increase your energy by $1$. You may use the shop multiple times, but you cannot make your energy exceed your energy cap. The energy cap of person $j$ is $U_j$. Everyone starts with energy $0$.

Person $j$ starts on floor $S_j$, and they want to reach floor $T_j$.

For each person, answer the minimum number of coins needed to reach their destination, or state that it is impossible.

Input Format

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

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

The third line contains $N$ integers $B_i$, representing the number of coins needed to buy energy at each floor’s shop.

The next $M$ lines each contain three integers $S_j, T_j, U_j$, describing one person.

Output Format

Output $M$ lines. Each line contains one integer, representing the minimum number of coins person $j$ needs to reach floor $T_j$.

If they cannot move to floor $T_j$, output $-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

Hint

Explanation of Sample 1

Person $1$ cannot reach floor $3$.

Person $2$ can reach floor $6$ in the following way:

• On floor $1$, spend $8$ coins to make their energy $4$.
• Move to floor $2$, and the energy becomes $1$.
• On floor $2$, spend $15$ coins to make their energy $4$.
• Move to floor $3$, and the energy becomes $0$.
• On floor $3$, spend $4$ coins to make their energy $4$.
• Move to floor $4$, and the energy becomes $3$.
• Move to floor $5$, and the energy becomes $2$.
• On floor $5$, spend $2$ coins to make their energy $4$.
• Move to floor $6$.

In total, $29$ coins are needed.

Constraints

This problem uses bundled testdata.

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

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

Notes

Translated from The 20th Japanese Olympiad in Informatics Final Round E ダンジョン 3 English translation Dungeon 3.

Translated by ChatGPT 5