Członkowie zespołu układającego zadania na konkurs SUA Programming Contest przygotowują zadania na zawody 2025 ICPC Wuhan Invitational Contest. Zadanie, nad którym obecnie pracują, posiada $n$ właściwości określających jego różne aspekty, takie jak trudność, długość kodu itp. Wartość $i$-tej właściwości wynosi $a_i$.

Członkowie zespołu zaproponowali również $q$ sugestii, gdzie $i$-tą sugestię można zapisać jako trzy liczby całkowite $p_i$, $l_i$ oraz $r_i$, co oznacza, że wartość $p_i$-tej właściwości powinna zawierać się w przedziale od $l_i$ do $r_i$ (włącznie).

BaoBao jest autorem zadania i zamierza zmodyfikować je zgodnie z tymi sugestiami. Może poświęcić jedną jednostkę czasu, aby zwiększyć lub zmniejszyć wartość właściwości o 1. Oblicz najmniejszą ilość czasu potrzebną na spełnienie wszystkich sugestii lub zgłoś, że jest to niemożliwe.

Wejście

Dostępnych jest wiele zestawów danych testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 100$) określającą liczbę zestawów danych. Dla każdego zestawu danych:

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $q$ ($1 \le n, q \le 100$), określające liczbę właściwości oraz liczbę sugestii.

Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), gdzie $a_i$ jest wartością $i$-tej właściwości.

Dla kolejnych $q$ linii, $i$-ta linia zawiera trzy liczby całkowite $p_i$, $l_i$ oraz $r_i$ ($1 \le p_i \le n$, $1 \le l_i \le r_i \le 10^9$), wskazujące, że wartość $p_i$-tej właściwości powinna zawierać się w przedziale od $l_i$ do $r_i$ (włącznie).

Wyjście

Dla każdego zestawu danych wypisz w jednej linii liczbę całkowitą określającą najmniejszą ilość czasu potrzebną na spełnienie wszystkich sugestii. Jeśli jest to niemożliwe, wypisz -1.

Przykład

Wejście 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

Wyjście 1

6
-1
0

Uwagi

Dla pierwszego przykładowego zestawu danych, BaoBao może zmienić 1. właściwość na 15, a 3. właściwość na 5. Odpowiedź wynosi $(20 - 15) + (5 - 4) = 6$.

Dla trzeciego przykładowego zestawu danych, ponieważ $3 \le 7 \le 9$ oraz $4 \le 7 \le 15$, wszystkie sugestie są już spełnione i BaoBao nie musi zmieniać żadnej właściwości.