Flattening the Mountain

A mountain in Ddasland consists of $N$ positions. Initially, the height of position $i$ is $A_i$.

Dadas has $M$ bombs. Bomb $j$ can be used on the interval $[L_j,R_j]$ and costs $W_j$. When it is used, the current height $H_i$ of every position $i$ in the interval becomes $\max(0,H_i-1)$.

Each bomb may be used at most once. Bombs may be left unused, and they may be used in any order.

Find the minimum total cost required to make every height equal to $0$. If this is impossible, print $-1$.

The input is given from Standard Input in the following format:

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

Each case is given in the following format:

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

For each test case, print the minimum total cost required to make every height equal to $0$ on one line.

If it is impossible, print $-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$).
• The sum of $N$ over all test cases does not exceed $2\,000$.
• The sum of $M$ over all test cases does not exceed $2\,000$.