遗址发掘（arche）

题目描述

Y 同学被委派负责一项大型考古工程。在一条长度为 $N$ 的线性区域内，地表被划分为 $N$ 个连续的单元格，编号依次为 $1, 2, \dots, N$。

为了发掘埋藏在底下的文物，Y 同学需要对这些单元格进行开掘。由于各区域的地质条件不同，开掘第 $i$ 个单元格需要支付 $c_i$ 的劳务费用。

根据前期探测，该区域内共有 $M$ 处潜在的遗址项目。第 $j$ 个项目覆盖了区间 $[l_j, r_j]$ 内的所有单元格。只有当该区间内每一个单元格都经过开掘后，该遗址的考古价值才能被提取，从而为 Y 同学带来 $w_j$ 的收益。

同一单元格可以被多个遗址项目共享。Y 同学可以自行决定开掘哪些单元格，以使得最终获得的利润（总收益减去总劳务费用）最大。请注意，Y 同学可以选择不进行任何开掘工作，此时利润为 $0$。

输入格式

第一行包含两个正整数 $N$ 和 $M$。

接下来的 $N$ 行，第 $i$ 行包含一个非负整数 $c_i$，表示开掘第 $i$ 个单元格的费用。

接下来的 $M$ 行，每行包含三个正整数 $l_j, r_j, w_j$，表示第 $j$ 个遗址项目覆盖的区间左端点、右端点以及该遗址的考古价值。

输出格式

输出一行一个整数，表示 Y 同学所能获得的最大利润。

样例

样例输入 #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

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N, M \le 2 \cdot 10^5$，$0 \le c_i \le 10^9$，$1 \le l_j \le r_j \le N$，$1 \le w_j \le 10^9$。

测试点编号	分值	$N \le$	$M \le$	特殊性质

| :----------: | :--: | :-----: | :-----: | :--------: | | $1 \sim 2$ | $10$ | $10$ | $10$ | 无 | | $3 \sim 6$ | $20$ | $300$ | $300$ | 无 | | $7 \sim 10$ | $20$ | $2 \cdot 10^5$ | $2 \cdot 10^5$ | 特殊性质 A | | $11 \sim 14$ | $20$ | $2 \cdot 10^5$ | $2 \cdot 10^5$ | 特殊性质 B | | $15 \sim 18$ | $20$ | $2 \cdot 10^5$ | $2 \cdot 10^5$ | 无 | | $19 \sim 20$ | $10$ | $2 \cdot 10^5$ | $2 \cdot 10^5$ | 无 |

* 特殊性质 A：对于所有的 $j$，满足 $l_j = 1$。 * 特殊性质 B：对于所有的 $j$，满足 $l_j = r_j$。