문제

$N + 1$ 層からなるダンジョンがあり，ダンジョン内には $M$ 人のプレイヤーがいる．ダンジョンの階層には入口から近い順に第 $1$ 層から第 $N + 1$ 層までの番号が付いている．また，プレイヤーには $1$ から $M$ までの番号が付いている．

ダンジョンのある階層から次の階層へ進むには体力を要する．プレイヤーは，第 $i$ 層（$1 \le i \le N$）から第 $i + 1$ 層に進む際に体力を $A_i$ 消費する．また，このダンジョンは一方通行であり，可能な階層間の移動は第 $i$ 層（$1 \le i \le N$）から第 $i + 1$ 層への移動のみである．

第 $1$ 層から第 $N$ 層までの各階層には $1$ つの回復の泉がある．第 $i$ 層（$1 \le i \le N$）にある回復の泉では，プレイヤーは $B_i$ 枚のコインを消費することで体力を $1$ 回復させることができる．回復の泉は，コインがある限り何回でも使用することができる．ただし，プレイヤーの体力には上限があり，回復の泉を使っても，体力がその上限を超えることはない．

プレイヤー $j$（$1 \le j \le M$）は現在第 $S_j$ 層にいる．現在の体力は $0$ であり，体力の上限は $U_j$ である．プレイヤー $j$ は，体力を $0$ 未満にすることなく第 $T_j$ 層まで進もうとしている．そのためには何枚のコインが必要であろうか．

ダンジョンの情報と各プレイヤーの情報が与えられたとき，各プレイヤーが体力を $0$ 未満にせずに目標の階層まで進むことが可能かを判定し，可能な場合には必要なコインの枚数の最小値を求めるプログラムを作成せよ．

입력

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

$N$ $M$
$A_1$ $\ldots$ $A_N$
$B_1$ $\ldots$ $B_N$
$S_1$ $T_1$ $U_1$
$\vdots$
$S_M$ $T_M$ $U_M$

출력

標準出力に $M$ 行で出力せよ．第 $j$ 行目（$1 \le j \le M$）にはプレイヤー $j$ が第 $T_j$ 層まで進むために必要なコインの枚数の最小値を出力せよ．ただし，プレイヤー $j$ が第 $T_j$ 層まで進むことができない場合は $-1$ を出力せよ．

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

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

제한

• $1 \le N \le 200\,000$．
• $1 \le M \le 200\,000$．
• $1 \le A_i \le 200\,000$（$1 \le i \le N$）．
• $1 \le B_i \le 200\,000$（$1 \le i \le N$）．
• $1 \le S_j < T_j \le N + 1$（$1 \le j \le M$）．
• $1 \le U_j \le 100\,000\,000$（$1 \le j \le M$）．

서브태스크

1. ($11$ 점) $N \le 3\,000$，$M \le 3\,000$．
2. ($14$ 점) $U_1 = U_2 = \ldots = U_M$．
3. ($31$ 점) $T_j = N + 1$（$1 \le j \le M$）．
4. ($44$ 점) 追加の制約はない．

プレイヤー $1$ は，体力の上限が $3$ であるため，第 $2$ 層から第 $3$ 層へ進むことができない．そのため，$1$ 行目の出力は $-1$ となる．

一方で，プレイヤー $2$ は体力の上限が $4$ であるため，以下のようにして第 $6$ 層まで進むことができる．

• 第 $1$ 層でコインを $8$ 枚使って体力を $4$ にし，第 $2$ 層に進む．このとき，体力は $1$ となる．
• 第 $2$ 層でコインを $15$ 枚使って体力を $4$ にし，第 $3$ 層に進む．このとき，体力は $0$ となる．
• 第 $3$ 層でコインを $4$ 枚使って体力を $4$ にし，第 $4$ 層に進む．このとき，体力は $3$ となる．
• 第 $4$ 層ではコインを使わずに，第 $5$ 層に進む．このとき，体力は $2$ となる．
• 第 $5$ 層でコインを $2$ 枚使って体力を $4$ にし，第 $6$ 層に進む．このとき，体力は $0$ となる．

合計 $29$ 枚のコインを使う．$29$ 枚未満のコインで第 $6$ 層まで進むことはできないので，$2$ 行目の出力は $29$ となる．

この入力例は小課題 $3$ の制約を満たしている．