区间降温

一排 $n$ 个温度计的初始读数为 $a_1,a_2,\ldots,a_n$．小宁有 $m$ 张降温卡，第 $j$ 张卡写有区间 $[l_j,r_j]$ 和正整数 $d_j$．使用这张卡会让编号从 $l_j$ 到 $r_j$（包含两个端点）的每个读数都减少 $d_j$．每张卡最多使用一次，使用次序不限，也可以一张都不使用．不同卡的区间和降温量可以相同，它们仍然是不同的卡．

最终读数中的最大值与最小值之差称为温差．请你求出最大的可能温差．读数可以为负数；只有一个温度计时温差为 $0$．

输入格式

第一行输入两个整数 $n,m$，分别表示温度计和降温卡的数量．

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始读数．

接下来 $m$ 行，第 $j$ 行输入三个整数 $l_j,r_j,d_j$，表示第 $j$ 张卡的区间和降温量．

输出格式

输出一个整数，表示最大可能温差．

样例 1

3 1
3 1 4
1 2 2

5

使用唯一的降温卡后，读数为 $1,-1,4$，温差为 $4-(-1)=5$．

更多样例

点击下载本题选手目录

下发样例独立构造，用于本地自测．通过这些样例不保证获得某个子任务的分数．

数据范围与子任务

所有输入均为整数．$1\le n\le2\times10^5$，$0\le m\le2\times10^5$，$-10^9\le a_i\le10^9$，$1\le l_j\le r_j\le n$，$1\le d_j\le10^9$．答案可能超过 32 位有符号整数范围．

各子任务独立计分．只有通过某一子任务的全部测试点，才能获得该子任务的全部分数．除表中额外限制外，每个子任务均遵守上述完整数据范围．