산 밀어버리기

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

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

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

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

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

$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$

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

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

• $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$ 이하이다.