E. Гонки в Линейном Королевстве
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Вы — организатор гонок, и вы хотите провести серию заездов в Линейном Королевстве.

В Линейном Королевстве n дорог, пронумерованных от 1 до n. Дороги идут одна за другой слева направо, в порядке возрастания номера. Вам поступило несколько предложений проведения заездов. Для каждого заезда известно, на каких дорогах предлагается его проводить — некоторый набор последовательных дорог Королевства. Также известно ваше вознаграждение, в случае если вы решите провести данный заезд. Все заезды предлагается проводить в разное время, то есть одна и та же дорога может использоваться в нескольких заездах.

К несчастью, некоторые дороги в плохом состоянии, и их нужно чинить. Для каждой дороги известна стоимость ее ремонта. Заезд можно проводить только если отремонтированы все дороги, на которых проходит гонка. Ваша задача — отремонтировать такой набор дорог (возможно, все, или ни одной), чтобы ваша прибыль была как можно больше. Прибыль считается как сумма вознаграждений, полученных за проведение заездов, минус сумма денег, потраченных на ремонт дорог. Заметьте, что вы можете не чинить дороги вообще и получить нулевую прибыль.

Найдите максимальную возможную прибыль.

Входные данные

В первой строке через пробел записано два целых числа n и m (1 ≤ n, m ≤ 2·105) — количество дорог и предложенных заездов соответственно.

Далее следует n строк. Каждая строка содержит одно целое неотрицательное число, не превосходящее 109 — стоимость починки очередной дороги. Стоимости починки даны в порядке начиная с дороги номер 1 заканчивая дорогой номер n.

Далее следует m строк по три числа в каждой: lb, ub, и p (1 ≤ lb ≤ ub ≤ n, 1 ≤ p ≤ 109). Каждая строка описывает очередной заезд: предлагается использовать дороги с lb по ub включительно, и вознаграждение будет составлять p.

Выходные данные

Выведите одно целое число — максимальную возможную прибыль, которую вы можете получить.

Пожалуйста, не используйте спецификатор %lld для чтения и записи 64-битных целых чисел в C++. Рекомендуется использовать потоки cin, cout (также вы можете использовать спецификатор %I64d).

Примеры
Входные данные
7 4
3
2
3
2
1
2
3
1 2 5
2 3 5
3 5 3
7 7 5
Выходные данные
4
Входные данные
2 1
0
3
1 2 5
Выходные данные
2
Входные данные
3 1
10
10
10
1 3 10
Выходные данные
0
Примечание

В первом примере выгодно чинить дороги 1, 2, 3 и 7. Три заезда приносят доход 15. Ремонт стоит 11, значит прибыль равна 4.