AT_past202010_o.宝箱

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

有一个长为 $n$ 的数列 $a$ 。现在有 $m$ 个区间，其中第 $i$ 个区间为 $[l_i,r_i]$ ，选择它的代价为 $c_i$ 。

你需要选出若干个区间，将这些区间去重后把所有被这些区间包含的数选出并相加。设被包含的数之和为 $y$ ，所花费的代价为 $x$ ，请输出 $y-x$ 的最大值。

第一行两个整数 $n,m$ 。

第二行 $n$ 个整数表示序列 $a$ 。

后面 $m$ 行，每行三个整数 $l_i,r_i,c_i$ 。

输出 $y-x$ 的最大值。

输入#1

4 3
20 10 100 10
1 3 100
2 4 50
1 1 50

输出#1

输入#3

20 10
40 28 12 29 34 89 37 64 48 53 81 95 46 42 77 76 49 59 14 15
2 11 221
14 20 14
2 11 126
1 8 273
5 11 94
2 8 48
12 15 83
2 7 13
5 16 269
3 12 115

输出#3

$1 \le n,m \le 2 \times 10^5$ ， $1 \le a_i,c_i \le 10^9$ ， $1 \le l_i \le r_i \le n$ 。

输入解题思路，AI测评打分。不知道怎么写?