SUA 程式設計競賽命題團隊的成員們正在為 2025 年 ICPC 武漢邀請賽準備題目。他們目前正在處理的題目有 $n$ 個屬性，用來表示題目的各個面向，例如難度、程式碼長度等。其第 $i$ 個屬性的值為 $a_i$。

成員們也提出了 $q$ 個建議，其中第 $i$ 個建議可以用三個整數 $p_i$、$l_i$ 和 $r_i$ 來表示，這意味著第 $p_i$ 個屬性的值應該介於 $l_i$ 和 $r_i$ 之間（包含邊界）。

BaoBao 是這道題目的作者，他將根據這些建議修改題目。他可以花費一個單位的時間將某個屬性的值增加或減少 1。請計算他為了滿足所有建議所需的最少時間，若無法滿足，則回報不可能。

輸入格式

輸入包含多組測試資料。第一行包含一個整數 $T$ ($1 \le T \le 100$)，表示測試資料的組數。對於每組測試資料：

第一行包含兩個整數 $n$ 和 $q$ ($1 \le n, q \le 100$)，分別表示屬性的數量和建議的數量。

第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，其中 $a_i$ 是第 $i$ 個屬性的值。

接下來的 $q$ 行中，第 $i$ 行包含三個整數 $p_i$、$l_i$ 和 $r_i$ ($1 \le p_i \le n, 1 \le l_i \le r_i \le 10^9$)，表示第 $p_i$ 個屬性的值應該介於 $l_i$ 和 $r_i$ 之間（包含邊界）。

輸出格式

對於每組測試資料，輸出一行包含一個整數，表示滿足所有建議所需的最少時間。如果無法滿足，則輸出 -1。

範例

範例輸入 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

範例輸出 1

6
-1
0

說明

對於第一組範例測試資料，BaoBao 可以將第 1 個屬性改為 15，將第 3 個屬性改為 5。答案為 $(20 - 15) + (5 - 4) = 6$。

對於第三組範例測試資料，由於 $3 \le 7 \le 9$ 且 $4 \le 7 \le 15$，所有建議已經滿足，BaoBao 不需要更改任何屬性。