该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

当圣诞节来临的时候，优优向圣诞老人许愿，希望能得到更多的糖果.

圣诞老人很慷慨，赐予了优优一种 最多使用 $m$次的"强大的魔法",能使她家对面 编号为 $l,l + 1,l + 2, \dots,r$ 的邻居得到了 $x$个糖果,即 $[l,r]$ 范围的内邻居得到了 $x$ 个糖果。

优优家对面有 $n$ 个邻居，最开始每个邻居家有 $a_i$个糖果,优优都可以去问他们要到所有糖果.

优优很调皮，想要随机给邻居们增加糖果数量，所以她使用 $m$ 次魔法,随机给 $[l,r]$ 范围内邻居 加上 $x$ 个糖果.(其中 $1 \le l \le r$)

请问最后优优能得到多少糖果?

输入格式

第一行输入两个整数 $n,m(1 \le m \le n \le {10^5})$

第二行$n$个整数 $a_i (1 \le a_i \le 10^9)$,表示第 $i$ 个 $(1 \le i \le n )$ 邻居家的糖果数量。

接下来的$m$ 行,每行输入三个整数 $l,r,x(1 \le l \le r \le n,1 \le x \le 10^9)$

表示给 $[l,r]$ 范围内邻居加上 $x$ 个糖果。

输出格式

输出一个整数，表示优优最后能拿到多少糖果。

样例

5 3
12 4 9 6 7
1 3 3
2 5 1
4 4 2

53

样例解释

最开始邻居家的糖果数量分别是 $12,4,9,6,7$

优优使用了 3 次魔法,

第一次魔法,给 $[1,3]$ 范围的邻居家的糖果数量加上 $3$ 个糖果,此时邻居家的糖果数量分别是 $15,7,12,6,7$

第二次魔法,给 $[2,5]$ 范围的邻居家的糖果数量加上 $1$ 个糖果,此时邻居家的糖果数量分别是 $15,8,13,7,8$

第三次魔法,给 $[4,4]$ 范围的邻居家的糖果数量加上 $2$ 个糖果,此时邻居家的糖果数量分别是 $15,8,13,9,8$

这样优优能拿到 $15 + 8 + 13 + 9 + 8 = 53$ 个糖果。

数据范围

对于$60\%$ 的数据, $1 \le m \le n \le 5000,1 \le l \le r \le n,1 \le a_i \le 10^5,1 \le x \le 10^5$

对于$100\%$的数据, $1 \le m \le n \le 10^5,1 \le l \le r \le n,1 \le a_i \le 10^9,1 \le x \le 10^9$