#408 Flattening the Mountain

Loading problem...

Preparing the statement, recent submissions, and submit form.

#408 Flattening the Mountain | DOJ

User Contest/EZ contest/EZ Contest Day 1

Authors: dyppp

Time limit: 3000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

KO EN

따스나라에는 $N$ 개의 위치로 이루어진 산이 있다. 처음에 $i$ 번째 위치의 높이는 $A_i$ 이다.

다다스는 $M$ 개의 폭탄을 가지고 있다. $j$ 번 폭탄은 구간 $[L_j,R_j]$ 에 사용할 수 있으며, 사용하는 데 $W_j$ 의 비용이 든다. 이 폭탄을 사용하면 구간 안의 각 위치 $i$ 에 대해, $i$ 번째 위치의 현재 높이를 $H_i$ 라고 할 때 $\max(0, H_i-1)$ 이 된다.

각 폭탄은 최대 한 번 사용할 수 있다. 폭탄을 사용하지 않아도 되며, 사용하는 순서는 자유롭게 정할 수 있다.

산의 모든 위치의 높이를 $0$ 으로 만드는 데 필요한 비용의 최솟값을 구하여라. 불가능하다면 $-1$ 을 출력하여라.

Input

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ M$ $A_1\ A_2\ \cdots\ A_N$ $L_1\ R_1\ W_1$ $L_2\ R_2\ W_2$ $\vdots$ $L_M\ R_M\ W_M$

Output

각 테스트 케이스마다, 산의 모든 높이를 $0$ 으로 만드는 데 필요한 비용의 최솟값을 한 줄에 출력한다.

불가능하다면 $-1$ 을 출력한다.

Constraints

$1 \leq T \leq 50$ .
$1 \leq N \leq 2\,000$ .
$0 \leq M \leq 2\,000$ .
$0 \leq A_i \leq 3$ ( $1 \leq i \leq N$ ).
$1 \leq L_j \leq R_j \leq N$ ( $1 \leq j \leq M$ ).
$0 \leq W_j \leq 10^9$ ( $1 \leq j \leq M$ ).
모든 테스트 케이스에 대한 $N$ 의 합은 $2\,000$ 이하이다.
모든 테스트 케이스에 대한 $M$ 의 합은 $2\,000$ 이하이다.

Subtasks

#	Score	Constraints
1	17	$N \leq 30$ . $M \leq 20$ .
2	19	모든 $i$ ( $1 \leq i \leq N$ )에 대해 $A_i \leq 1$ 이다.
3	24	$N \leq 300$ . $M \leq 300$ .
4	40	추가적인 제약이 없다.

Samples

Input

Output

6
-1
0

첫 번째 테스트 케이스에서는 $1$ 번 폭탄과 $2$ 번 폭탄을 사용하면 각 위치의 높이가 모두 $0$ 이 되며, 총비용은 $6$ 이다.

두 번째 테스트 케이스에서는 두 번째 위치를 덮는 폭탄이 없으므로 불가능하다.

세 번째 테스트 케이스에서는 처음부터 모든 높이가 $0$ 이므로 비용이 들지 않는다.

Editorial

View editorial

산 밀어버리기

Statement

Input

Output

Constraints

Subtasks

Samples

Editorial