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 不需要修改任何属性。