Members of the SUA Programming Contest Problem Setter Team are preparing problems for the 2025 ICPC Wuhan Invitational Contest. The problem they’re currently working on has $n$ properties to indicate its various aspects, such as difficulty, length of code, etc. The value of its $i$-th property is $a_i$.

The members have also proposed $q$ suggestions, where the $i$-th suggestion can be denoted as three integers $p_i$, $l_i$, and $r_i$, which means the value of the $p_i$-th property should lie between $l_i$ and $r_i$ (both inclusive).

BaoBao is the author of the problem, and he is going to modify the problem according to these suggestions. He can spend one unit of time to increase or decrease the value of a property by 1. Calculate the smallest amount of time he needs so that all suggestions are satisfied, or report that it is impossible to do so.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 100$) indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 100$), indicating the number of properties and the number of suggestions.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the value of the $i$-th property.

For the following $q$ lines, the $i$-th line contains three integers $p_i$, $l_i$, and $r_i$ ($1 \le p_i \le n$, $1 \le l_i \le r_i \le 10^9$), indicating that the value of the $p_i$-th property should lie between $l_i$ and $r_i$ (both inclusive).

Output

For each test case, output one line containing one integer, indicating the smallest amount of time needed to satisfy all suggestions. If it is impossible to do so, output -1 instead.

Examples

Input 1

3
4 3
20 25 4 27
3 5 7
1 10 15
3 2 6
1 2
7
1 3 5
1 9 9
1 2
7
1 3 9
1 4 15

Output 1

6
-1
0

Note

For the first sample test case, BaoBao can change the 1-st property to 15 and the 3-rd property to 5. The answer is $(20 - 15) + (5 - 4) = 6$.

For the third sample test case, as $3 \le 7 \le 9$ and $4 \le 7 \le 15$, all suggestions are already satisfied and BaoBao does not need to change any property.