페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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

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

입력
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
출력
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
출력
151
591
4
284
339
517
35
581
254
58
-1
178
519
-1
-1
-1
219
-1
-1
214

출처

JOI 2021

역링크 공식 문제집만