E. 线性王国的赛车比赛

时间限制：3 秒
内存限制：256 兆字节

你是一个赛车比赛的组织者，想要在线性王国安排一些比赛。

线性王国有 $n$ 条连续的道路，从左到右排列。道路编号为 $1$ 到 $n$，从左到右依次递增。这些道路上可能会举行若干场比赛。每场比赛使用一段连续的道路。同时，如果你举办了该场比赛，你会获得一定的金钱报酬。比赛不会在时间上重叠，因此同一条道路可以被多场比赛使用。

不幸的是，有些道路状况不佳，需要修复。每条道路都有对应的修复费用，你必须支付该费用才能修复它。一场比赛只有在它使用的所有道路都被修复的情况下才能举行。你的任务是选择修复一些道路（可以全部修复，也可以一条都不修），使得你的利润最大化。你的利润定义为：举办的所有比赛的总报酬 − 修复道路的总花费。注意，你可以选择不修复任何道路，从而获得 $0$ 利润。

输出你能获得的最大利润。

输入

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示道路的数量和比赛的数量。

接下来 $n$ 行，每行一个非负整数（不超过 $10^9$），表示从道路 $1$ 到道路 $n$ 的修复费用。

最后 $m$ 行，每行三个整数 $l_b, u_b, p$（$1 \le l_b \le u_b \le n$，$1 \le p \le 10^9$），表示一场比赛使用从 $l_b$ 到 $u_b$（包含两端）的所有道路，如果举办该比赛，你将获得 $p$ 的报酬。

输出

输出一个整数，表示你能获得的最大利润。

注意：在 C++ 中，请不要使用 %lld 来读写 64 位整数，推荐使用 cin / cout 流（也可以使用 %I64d 说明符）。

样例

样例输入 1

7 4
3
2
3
2
1
2
3
1 2 5
2 3 5
3 5 3
7 7 5

样例输出 1

4

样例输入 2

2 1
0
3
1 2 5

样例输出 2

2

样例输入 3

3 1
10
10
10
1 3 10

样例输出 3

0

样例解释

在第一个样例中，最优解是修复道路 $1,2,3,7$。三场比赛得以举行，总报酬为 $15$，修复花费为 $11$，因此利润为 $4$。