ダンジョン 3 (Dungeon 3)

Unrated

日本語

Language

Time limit: 3000 ms
Memory limit: 512 MB
Submissions: 0
Correct: 0
Solved by: 0
AC rate: —

Statement

\(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\) 未満にせずに目標の階層まで進むことが可能かを判定し，可能な場合には必要なコインの枚数の最小値を求めるプログラムを作成せよ．

Input

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

\(N\) \(M\)
\(A_1\) \(\cdots\) \(A_N\)
\(B_1\) \(\cdots\) \(B_N\)
\(S_1\) \(T_1\) \(U_1\)
\(\vdots\)
\(S_M\) \(T_M\) \(U_M\)

Output

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

Constraints

\(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\))．

Subtasks

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

Examples

Sample input 1

Sample output 1

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

Sample input 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

Sample output 2

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

Sample input 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

Sample output 3

Notes

JOI 2021 · JCIOI · CC BY-SA 4.0

Source

Olympiad › Japanese Olympiad in Informatics › JOI 2020-2021 Season › JOI 2021 Final Round5