题目背景

WuuTue拥有一家马戏团，马戏团会在全国巡演，最近WuuTue的马戏团来到了T市。

题目描述

T市有一条专门的演出街，演出街是一条东西走向的笔直街道，街道上从西往东有 $n$ 个舞台，舞台的编号为 $1, 2, \dots, n$。

WuuTue计划在T市的演出街上进行 $M$ 场演出，其中第 $i$ 场演出要占用从 $l_i$ 到 $r_i$ 的连续舞台（包括 $l_i$ 和 $r_i$ ），同时WuuTue知道，第 $i$ 场比赛将会获得 $v_i$ 元的收益。

由于演出街的舞台都是设计给人表演使用的，如果要供动物表演使用的话，需要进行加固，其中加固第 $i$ 个舞台需要花费 $c_i$ 元钱，并且只需要加固一次，可以重复使用。也就是说如果有多个演出都用到了舞台 $i$，那么只需要花费一次加固的费用就可以了。

当然，如果WuuTue发现某场演出可能由于加固费用过高无法盈利，也可能会取消演出。

因为WuuTue太蒻了，所以请帮助WuuTue计算，他最多可以获得多少元钱的收入。

输入格式

第一行：两个空格分隔的整数 $n$ 和 $m$，分别表示舞台和演出的数量。

第二到 $n+1$ 行：每行 $1$ 个整数，其中第 $i+1$ 行的整数表示加固第 $i$ 个舞台需要的花费 $c_i$。

第 $n+2$ 行到第 $n+m+1$ 行：每行 $3$ 个空格分隔的整数，其中第 $n+i+1$ 行的 $3$ 个整数 $l_i$，$r_i$，$v_i$，表示第 $i$ 场演出需要占用第 $l_i$ 到 $r_i$ 的连续舞台，可以获得 $v_i$ 元的收益。

输出格式

一行：一个整数，表示WuuTue可以获得的最大收益。

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

提示

本题采用捆绑测试

对于 $20\%$ 的数据， $1 \le n , m \le 100$。

另有 $20\%$ 的数据， $v_i = c_i = 1$。

另有 $20\%$ 的数据， $l_i = r_i$。

对于 $100\%$ 的数据， $1 \le n , m \le 10^6 , 0 \le v_i , c_i \le 10^9 , 1 \le l_i \le r_i \le n$。