来自钟浩曦
#include <cstdio>
#include <cctype>
#include <memory.h>
#include <algorithm>
using namespace std;
typedef long long LL;
int read() {
int s = 0, d;
bool nag = 0;
do {
d = getchar();
if (d == '-')
nag = 1;
} while (!isdigit(d));
do
s = s * 10 + d - 48, d = getchar();
while (isdigit(d));
return nag ? -s : s;
}

struct seg
{
int l, r;
LL v, z;
seg *ls, *rs;
};
struct obj
{
int l, r, v;
};
inline bool compare(const obj& a, const obj& b) {
return (a. l < b. l) || (a. l == b. l && a. r < b. r);
}
const int maxn=200009;
const LL inf=LLONG_MAX>>1;
int n,m;
obj q[maxn];
LL s[maxn],ans;
seg *rtf,*rtc,*sp;
#define mid(p)((p->l+p->r)>>1)
seg *build(int l, int r)
{
seg p = sp ++;
p->v=- inf;
p->z= 0;
p->l= l;
p->r=r;
if (l + 1 < r) {
p-> ls = build(l, mid(p));
p-> rs = build(mid(p), r);
}
return p;
}
void modfy(seg p, int p0, LL v0)
{
if (p-> l + 1 == p-> r)
p-> v = max(p-> v, v0);
else {
if (p0 < mid(p))
modfy(p-> ls, p0, v0 - p-> z);
else
modfy(p-> rs, p0, v0 - p-> z);
p-> v = max(p-> ls-> v, p-> rs-> v) + p-> z;
}
}
LL query(seg* p, int l, int r)
{
if (l >= r)
return -inf;
else if (p-> l == l && p-> r == r)
return p-> v;
else if (r <= mid(p))
return query(p-> ls, l, r) + p-> z;
else if (l >= mid(p))
return query(p-> rs, l, r) + p-> z;
else
return max(query(p-> ls, l, mid(p)), query(p-> rs, mid(p), r)) + p-> z;
}
void push_col(seg* p, int l, LL z0)
{
if (p-> v == -inf)return;
else if (p-> l == l)
p-> v += z0, p->z += z0;
else {
if (l < mid(p)) {
push_col(p-> ls, l, z0);
push_col(p-> rs, mid(p), z0);
}
else
push_col(p-> rs, l, z0);
p-> v = max(p-> ls-> v, p-> rs-> v) + p-> z;
}
}
int main()
{
n = read();
m = read();
rtf = build(0, n + 2);
rtc = build(0, n + 2);
s[0] = 0;
for (int i = 1; i <= n; i ++)
s[i] = s[i - 1] + read();
for (int i = 0; i < m; i ++)
{
q[i]. l = read();
q[i]. r = read();
q[i]. v = read();
}
sort(q,q+m,compare);
ans=0;
for(int i=0;i<m;i++)
{
LL res0 = max(query(rtf,0,q[i].l),0LL)-s[q[i]. r]+s[q[i].l-1];
LL res1 = query(rtc, q[i]. l, q[i]. r + 1) - s[q[i]. r];
LL res = max(max(res0, res1), query(rtf, q[i]. r, n + 1)) + q[i]. v;
push_col(rtf, q[i]. r, q[i]. v);
push_col(rtc, q[i]. r, q[i]. v);
modfy(rtf, q[i]. r, res);
modfy(rtc, q[i]. r, res + s[q[i]. r]);
ans = max(ans, res);
}
printf("%lld\n", ans);
}