CF115E.Linear Kingdom Races

You are a car race organizer and would like to arrange some races in Linear Kingdom.

Linear Kingdom has n consecutive roads spanning from left to right. The roads are numbered from 1 to n from left to right, thus the roads follow in the order of their numbers' increasing. There will be several races that may be held on these roads. Each race will use a consecutive subset of these roads. Also, each race will pay some amount of money to you if this race is held. No races overlap in time, so some roads can be used in several races.

Unfortunately, some of the roads are in a bad condition and they need repair. Each road has repair costs associated with it, you are required to pay this cost to repair the road. A race can only take place if all the roads used in the race are renovated. Your task is to repair such roads (possibly all or none) that will maximize your profit. Your profit is defined as the total money you get from the races that are held minus the total money you spent to repair the roads. Note that you may decide not to repair any road and gain zero profit.

Print the maximum profit you can gain.

你是一名赛车比赛组织者，希望在“线性王国”中举办若干场比赛。

“线性王国”拥有从左到右连续排列的 $n$ 条道路。这些道路从左到右依次编号为 $1$ 到 $n$，因此道路顺序与其编号递增顺序一致。将在这些道路上举行若干场比赛。每场比赛将使用其中一段连续的道路子集。此外，若某场比赛得以举行，它将向你支付一定金额的报酬。由于各场比赛在时间上互不重叠，因此同一条道路可被多场比赛共用。

不幸的是，部分道路状况不佳，需要维修。每条道路均对应一个维修费用，你必须支付该费用才能完成维修。一场赛事仅当其所使用的所有道路均已被维修后，方可举行。你的任务是选择需维修的道路集合（可能全部维修、也可能一条都不修），以使你的总收益最大化。你的收益定义为：所有成功举行的赛事所支付的报酬总额，减去你为维修道路所支出的总费用。注意，你可以选择不维修任何道路，从而获得零收益。

请输出你能获得的最大收益。

The first line contains two single-space separated integers, n and m (1 ≤ n, m ≤ 2·105), denoting the number of roads and the number of races, respectively.

Then n lines follow, each line will contain a single non-negative integer not exceeding 109 denoting the cost to repair a road. The costs are given in order from road 1 to road n.

Finally, m lines follow. Each line is single-space-separated triplets of integers. Each triplet will be given as lb, ub, and p (1 ≤ lb ≤ ub ≤ n, 1 ≤ p ≤ 109), which means that the race these three integers describe will use all the roads from lb to ub, inclusive, and if it's held you get p.

第一行包含两个以单个空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^5$），分别表示道路的数量和比赛的数量。

接下来是 $n$ 行，每行包含一个不超过 $10^9$ 的非负整数，表示修复对应道路的费用。这些费用按道路编号从 1 到 $n$ 的顺序给出。

最后是 $m$ 行，每行包含三个以单个空格分隔的整数构成的三元组。每个三元组形如 $lb$、$ub$ 和 $p$（$1 \leq lb \leq ub \leq n$，$1 \leq p \leq 10^9$），表示该三元组所描述的比赛将使用从道路 $lb$ 到道路 $ub$（含端点）的所有道路；若举办该比赛，则可获得收益 $p$。

Print a single integer denoting the maximum possible profit you can gain.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is recommended to use cin, cout stream (also you may use %I64d specificator).

输出一个整数，表示你能获得的最大可能利润。

请注意，在 C++ 中不要使用 %lld 格式说明符来读取或写入 64 位整数。建议使用 cin、cout 流（你也可以使用 %I64d 格式说明符）。

In the first sample the optimal solution is to repair roads 1, 2, 3, and 7. Three races will take place which nets you 15. The road repair costs 11, hence your profit is 4.

在第一个样例中，最优方案是修复道路 1、2、3 和 7。将举行三场赛车比赛，共获得收益 15。道路修复花费为 11，因此你的利润为 4。