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

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

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

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

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

制約

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

小課題

1. (11 点) N \leqq 3\,000，M \leqq 3\,000．
2. (14 点) U_1 = U_2 = \cdots = U_M．
3. (31 点) T_j = N+1 (1 \leqq j \leqq M)．
4. (44 点) 追加の制約はない．

入力例 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

プレイヤー 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 となる．

入力例 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 の制約を満たしている．

入力例 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