페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5870
서브태스크

던전 3 4초 512MB

문제

N + 1 층으로 구성된 던전이 있으며 던전에는 M 명의 플레이어가 있다. 던전의 계층에는 입구에서 가까운 순서로 1 층부터 N+1 층까지의 번호가 붙어 있다. 또한 플레이어는 1에서 M까지 번호가 매겨져 있다.

던전의 한 계층에서 다음 계층으로 진행하려면 체력이 필요하다. 플레이어는 i 층 (1 ≤ i ≤ N)에서 i + 1 층으로 진행할 때 체력을 A_i 소비한다.

또한 이 던전은 일방통행이라 계층 간의 이동은 i 층 (1 ≤ i ≤ N)에서 i + 1 층으로의 이동만 가능하다.

각 층에는 하나의 회복 분수가 있다. i 층 (1 ≤ i ≤ N)에 있는 회복 분수에서 플레이어는 B_i 장의 동전을 소비하여 체력을 1 회복시킬 수 있다.

회복 분수는 동전이 있는 한 여러 번 사용할 수 있다. 그러나 플레이어의 체력에는 상한이 있으며, 회복 분수를 사용해도 체력이 그 상한을 초과하지는 않는다.

플레이어 j (1 ≤ j ≤ M)는 현재 S_j 계층에 있다. 현재 체력은 0이고 체력의 상한은 U_j입니다. 플레이어 j는 체력을 0보다 작게하지 않고 제 T_j 층까지 진행하려고 한다. 그러기 위해서는 몇 장의 동전이 필요할지 알아보자.

던전의 정보와 각 플레이어의 정보가 주어졌을 때, 각 플레이어가 체력을 0 미만으로 하지 않고 목표의 계층까지 진행할 수 있는지 판정해, 가능한 경우에는 필요한 코인의 매수의 최소치를 출력하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 표준 입력에서 제공된다. 입력 된 모든 값은 정수다.

N M

A_1 · · · A_N

B_1 · · · B_N

S 1 T_1 U_1

\vdots

S M T_M U_M

[제한]

• 1 ≤ N ≤ 200\, 000.

• 1 ≤ M ≤ 200 \,000.

• 1 ≤ A_i ≤ 200\, 000 (1 ≤ i ≤ N).

• 1 ≤ B_i ≤ 200 \,000 (1 ≤ i ≤ N).

• 1≤S_j<T_j≤N+1(1≤j≤M).

• 1 ≤ U_j ≤ 100 \,000 \,000 (1 ≤ j ≤ M).


출력

표준 출력에 M 행으로 출력하라. 제 j 행 (1 ≤ j ≤ M)은 플레이어 j가 제 T j 레이어까지 진행하는 데 필요한 코인의 매수의 최소값을 출력하라. 단, 플레이어 j는 제 T j 레이어까지 진행할 수 없다. 그렇다면 -1을 출력하십시오.


부분문제

번호 점수 조건
#111점

N ≤ 3 000, M ≤ 3 000

#214점

U_1 = U_2 = · · · = U_M

#331점

T_j = N + 1 (1 ≤ j ≤ M)

#444점

추가 제약이 없다.


예제1

입력
54
34114
25121
163
164
351
259
출력
-1
29
3
22

플레이어 1은 체력의 상한이 3이므로 제 2 층에서 제 3 층으로 진행할 수 없다. 따라서 첫 번째 행의 출력은 -1입니다.

한편, 플레이어 2는 체력의 상한이 4이므로, 다음과 같이 하여 6층까지 진행할 수 있다.

• 첫 번째 레이어에서 8 개의 동전을 사용하여 체력을 4로 만들고 두 번째 레이어로 이동합니다. 이때 체력은 1이 된다.

• 두 번째 레이어에서 15 개의 동전을 사용하여 체력을 4로 설정하고 세 번째 레이어로 이동합니다. 이 때 체력은 0입니다.

• 3층에서 동전을 4장 사용하여 체력을 4로 하고, 4층으로 진행한다. 이때 체력은 3이 된다.

• 네 번째 레이어에서는 동전을 사용하지 않고 다섯 번째 레이어로 진행합니다. 이때 체력은 2가 된다.

• 5 층에서 동전 2 장을 사용하여 체력을 4로 만들고 6 층으로 진행합니다. 이 때 체력은 0입니다.

총 29 장의 동전을 사용합니다. 29장 미만의 코인으로 6층까지 진행할 수 없기 때문에, 2행째의 출력은 29가 된다.


예제2

입력
1010
18981571066
1010281039837
21128
51128
71128
11118
31118
81118
41111
61111
101111
9115
출력
208
112
179
248
158
116
234
162
42
-1

예제3

입력
2020
2321146915171481731220419845
193182137519101128115201132186
121567
71518
161714
92197
11943
31831
162070
72028
11661
3569
91015
213134
111923
162014
52116
152011
71154
71616
131710
315135
출력
151
591
4
284
339
517
35
581
254
58
-1
178
519
-1
-1
-1
219
-1
-1
214

출처

JOI 2021

역링크