시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

There is a dungeon with N + 1 floors. There are M players in the dungeon. The floors are numbered from 1 to N + 1, starting from the entrance. The players are numbered from 1 to M.

A player uses energy to move from a floor to the next floor. The amount of energy a player uses is Ai if he moves from the floor i (1 ≤ i ≤ N) to the floor i + 1. As this is a one-way dungeon, the only possible moves between floors are from the floor i to the floor i + 1 for some i (1 ≤ i ≤ N).

In each of the floors from the floor 1 to the floor N, inclusive, there is a fountain of recovery. At the fountain of recovery in the floor i (1 ≤ i ≤ N), a player can increase his energy by 1 paying Bi coins. A player can use a fountain multiple times as long as he has needed coins. However, each player has a maximum value of his energy, and his energy cannot exceed that value even if he uses a fountain of recovery.

Now the player j (1 ≤ j ≤ M) is in the floor Sj. His current energy is 0. His maximum value of energy is Uj. He wants to move to the floor Tj. His energy cannot be smaller than 0 along the way. How many coins does he need?

Write a program which, given the information of the dungeon and the players, determines whether it is possible for each player to move to the destination so that his energy does not become smaller than 0 along the way. If it is possible to move, the program should calculate the minimum number of coins he needs.

입력

Read the following data from the standard input. Given values are all integers.

N M
A1 · · · AN
B1 · · · BN
S1 T1 U1
.
.
.
SM TM UM

출력

Write M lines to the standard output. The j-th line (1 ≤ j ≤ M) should contain the minimum number of coins the player j needs to move to the floor Tj. If it is impossible for the player j to move to the floor Tj, output −1 instead.

제한

  • 1 ≤ N ≤ 200 000.
  • 1 ≤ M ≤ 200 000.
  • 1 ≤ Ai ≤ 200 000 (1 ≤ i ≤ N).
  • 1 ≤ Bi ≤ 200 000 (1 ≤ i ≤ N).
  • 1 ≤ Sj < Tj ≤ N + 1 (1 ≤ j ≤ M).
  • 1 ≤ Uj ≤ 100 000 000 (1 ≤ j ≤ M)

예제 입력 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

-1
29
3
22

Since the maximum value of energy of the player 1 is 3, the player 1 cannot move from the floor 2 to the floor 3. Hence the first line of output is −1.

On the other hand, the maximum value of energy of the player 2 is 4. The player 2 can move to the floor 6 by the following way.

  • In the floor 1, he pays 8 coins, and his energy becomes 4. Then he moves to the floor 2, and his energy becomes 1.
  • In the floor 2, he pays 15 coins, and his energy becomes 4. Then he moves to the floor 3, and his energy becomes 0.
  • In the floor 3, he pays 4 coins, and his energy becomes 4. Then he moves to the floor 4, and his energy becomes 3.
  • In the floor 4, he does not pay coins. Then he moves to the floor 5, and his energy becomes 2.
  • In the floor 5, he pays 2 coins, and his energy becomes 4. Then he moves to the floor 6, and his energy becomes 0.

In total, the player 2 pays 29 coins. Since it is impossible for the player 2 to move to the floor 6 by paying less than 29 coins, the second line of output is 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

예제 출력 2

208
112
179
248
158
116
234
162
42
-1

예제 입력 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

예제 출력 3

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