小翔和泰拉瑞亚
题号：NC54586
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

小翔爱玩泰拉瑞亚 。
一天，他碰到了一幅地图。这幅地图可以分为n列，第i列的高度为Hi，他认为这个地图不好看，决定对它进行改造。
小翔又学会了m个魔法，实施第i个魔法可以使地图的第Li列到第Ri列每一列的高度减少Wi，每个魔法只能实施一次，魔法的区间可能相交或包含。
小翔认为，一幅地图中最高的一列与最低的一列的高度差越大，这幅地图就越美观。
小翔可以选择m个魔法中的任意一些魔法来实施，使得地图尽量美观。但是他不知道该如何选择魔法，于是他找到了你。请你求出所有可行方案中，高度差的最大值。
对于100%的数据，满足1≤n,m≤200000,-109≤Hi≤109,1≤Wi≤109,1≤Li≤Ri≤n。

输入描述:

输入文件的第一行包含两个整数n,m。
输入的第二行包含n个整数，相邻两数间用一个空格隔开，第i个整数为Hi。
接下来的m行，每行包含3个整数，分别是Li,Ri,Wi，相邻两数间用一个空格隔开。

输出描述:

一行一个整数，表示高度差的最大值。
示例1

输入

复制 
3 3
7 -2 -10
1 3 4
3 3 4
1 2 8

输出

复制 
21