← 返回题目列表

Codeforces · 115/E

E. 线性王国种族

中文机器翻译题面 查看原题

您是一名汽车比赛组织者,想在线性王国安排一些比赛。

线性王国有 n 条从左到右连续的道路。道路从左到右编号为 1 到 n,因此道路按照编号递增的顺序排列。这些道路上可能会举行几场比赛。每场比赛将使用这些道路的连续子集。另外,如果举办该比赛,每场比赛都会向您支付一定的金钱。比赛时间不会重叠,因此某些道路可以在多场比赛中使用。

不幸的是,有些道路状况不佳,需要维修。每条道路都有与之相关的维修费用,您需要支付这笔费用来维修道路。只有比赛使用的所有道路都经过翻新后,比赛才能举行。您的任务是修复这些道路(可能全部或没有),以使您的利润最大化。您的利润定义为您从举办的比赛中获得的总资金减去您用于修复道路的总资金。请注意,您可能决定不修复任何道路并获得零利润。

打印您可以获得的最大利润。

输入

第一行包含两个单空格分隔的整数n和m(1≤n,m≤2·105),分别表示道路数量和比赛数量。

接下来是n行,每行包含一个不超过109的非负整数,表示修复道路的成本。成本按从道路 1 到道路 n 的顺序给出。

最后是 m 行。每一行都是单空格分隔的整数三元组。每个三元组将被指定为 lb、ub 和 p(1 ≤ lb ≤ ub ≤ n,1 ≤ p ≤ 109),这意味着这三个整数描述的比赛将使用从 lb 到 ub 的所有道路(包括在内),如果满足,您将获得 p。

输出

打印一个整数,表示您可以获得的最大可能利润。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。推荐使用 cin、cout 流(也可以使用 %I64d 指定符)。

示例

输入 #1

7 4
3
2
3
2
1
2
3
1 2 5
2 3 5
3 5 3
7 7 5

输出 #1

4

输入 #2

2 1
0
3
1 2 5

输出 #2

2

输入 #3

3 1
10
10
10
1 3 10

输出 #3

0

注意

在第一个示例中,最佳解决方案是修复道路 1、2、3 和 7。将举行三场比赛,您将获得 15 分。道路修复成本为 11,因此您的利润为 4。