Члены команды составителей задач SUA готовят задачи для 2025 ICPC Wuhan Invitational Contest. Задача, над которой они сейчас работают, имеет $n$ свойств, характеризующих её различные аспекты, такие как сложность, длина кода и т. д. Значение $i$-го свойства равно $a_i$.

Участники также предложили $q$ пожеланий, где $i$-е пожелание можно обозначить тремя целыми числами $p_i$, $l_i$ и $r_i$, что означает, что значение $p_i$-го свойства должно находиться в диапазоне от $l_i$ до $r_i$ включительно.

Баобао — автор задачи, и он собирается изменить задачу в соответствии с этими пожеланиями. Он может потратить одну единицу времени, чтобы увеличить или уменьшить значение свойства на 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

Примечание

Для первого примера Баобао может изменить 1-е свойство на 15, а 3-е свойство на 5. Ответ равен $(20 - 15) + (5 - 4) = 6$.

Для третьего примера, так как $3 \le 7 \le 9$ и $4 \le 7 \le 15$, все пожелания уже выполнены, и Баобао не нужно менять никакие свойства.