#408 Flattening the Mountain

Statement

Statement language

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 . When it is used, the current height of every position in the interval becomes .

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

Input

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

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

Output

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

Constraints

$1 \leq T \leq 50$ .
$1 \leq N \leq 2\,000$ .
$0 \leq M \leq 2\,000$ .

Subtasks

#	Score	Constraints
1	17	$N \leq 30$ . $M \leq 20$ .
2	19	$A_i \leq 1$ for every ().

Samples

Input

Output

6
-1
0

In the first test case, using bombs $1$ and $2$ makes every height equal to $0$ with total cost $6$ .

In the second test case, no bomb covers the second position, so it is impossible.

In the third test case, every height is already $0$ , so the answer is .