AT_joi2021ho_e ダンジョン 3 (Dungeon 3)

[problemUrl]: https://atcoder.jp/contests/joi2021ho/tasks/joi2021ho_e $ 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 $ 未満にせずに目標の階層まで進むことが可能かを判定し，可能な場合には必要なコインの枚数の最小値を求めるプログラムを作成せよ． - - - - - -

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である． > $ 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 $

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

### 制約 - $ 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\