SUA Programming Contest Problem Setter Teamのメンバーは、2025年ICPC Wuhan Invitational Contestに向けた問題を作成しています。現在取り組んでいる問題には、難易度やコードの長さなど、さまざまな側面を示す $n$ 個のプロパティがあります。$i$ 番目のプロパティの値は $a_i$ です。

メンバーは $q$ 個の提案も行いました。$i$ 番目の提案は3つの整数 $p_i, l_i, r_i$ で表され、$p_i$ 番目のプロパティの値が $l_i$ 以上 $r_i$ 以下（両端を含む）でなければならないことを意味します。

BaoBaoはこの問題の作成者であり、これらの提案に従って問題を修正しようとしています。彼は1単位の時間を使うことで、プロパティの値を1だけ増減させることができます。すべての提案を満たすために必要な最小の時間を計算してください。もし不可能であれば、その旨を報告してください。

入力

入力は複数のテストケースから構成されます。入力の最初の行には、テストケースの数を示す整数 $T$ ($1 \le T \le 100$) が含まれます。各テストケースは以下の通りです。

最初の行には、プロパティの数と提案の数を示す2つの整数 $n$ と $q$ ($1 \le n, q \le 100$) が含まれます。

2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) が含まれます。ここで $a_i$ は $i$ 番目のプロパティの値です。

続く $q$ 行には、$i$ 番目の提案として3つの整数 $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 を出力してください。

入出力例

入力 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番目のサンプルテストケースでは、$3 \le 7 \le 9$ かつ $4 \le 7 \le 15$ であるため、すべての提案はすでに満たされており、BaoBaoはどのプロパティも変更する必要はありません。