← 返回题目列表

AtCoder · past202010_o

O. 宝箱

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

分数: 6 点

警告

2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

你发现 N 宝箱已编号 1 通过 N。 最初,所有箱子都被锁住,无法打开。 如果您成功解锁宝箱 i,你得到 a_i 日元(日本的货币)。

在你的朋友中,有 M 锁匠,编号 1 通过 M。 如果你问锁匠 i 通过付费解锁宝箱 c_i 日元,锁匠将解锁所有仍锁在箱子中的箱子 l_i, l_i + 1, \ldots, r_i.

您的目标是最大化 Y-X,其中 X 是您支付给锁匠的总金额,并且 Y 是您从宝箱中获得的总金额。找出最大可能值 Y-X.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N,M \leq 2 \times 10^5
  • 1 \leq a_i,c_i \leq 10^9
  • 1 \leq l_i \leq r_i \leq N

输入

输入由标准输入按以下格式给出:

N M
a_1 a_2 \cdots a_N
l_1 r_1 c_i
\vdots
l_M r_M c_M

输出

打印最大可能值 Y-X,其中 X 是您支付给锁匠的总金额,并且 Y 是您从宝箱中获得的总金额。


示例输入 1

4 3
20 10 100 10
1 3 100
2 4 50
1 1 50

示例输出 1

70
  • 最好支付 50 日元 到 锁匠 2 并得到 10+100+10=120 解锁宝箱获得的日元 2,3,4.
  • 请注意,您不必解锁所有箱子。

示例输入 2

2 2
10 10
1 1 1000
1 2 100

示例输出 2

0
  • 请注意,最佳策略可能不是要求任何锁匠解锁箱子。

示例输入 3

20 10
40 28 12 29 34 89 37 64 48 53 81 95 46 42 77 76 49 59 14 15
2 11 221
14 20 14
2 11 126
1 8 273
5 11 94
2 8 48
12 15 83
2 7 13
5 16 269
3 12 115

示例输出 3

760