← 返回题目列表

AtCoder · past202209_m

M. 系列

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

分数: 6 点

问题陈述

有一系列漫画,包括 N 书籍。的 i-th (1 \leq i \leq N) 本书售价为 A_i 日元。

这些书也是成套出售的。有 M 设置, j-th (1 \leq j \leq M) 的售价为 B_j 日元并包含 L_j-th, (L_j + 1)-th, \ldots, R_j该系列的第 3 本书。

至少需要支付多少日元才能获得其中至少一种 N 书籍?

约束

  • 1 \leq N, M \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 \, (1 \leq i \leq N)
  • 1 \leq B_j \leq 10^9 \, (1 \leq j \leq M)
  • 1 \leq L_j \leq R_j \leq N \, (1 \leq j \leq M)
  • 输入中的所有值都是整数。

输入

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

N M
A_1 \ldots A_N
B_1 L_1 R_1
\vdots
B_M L_M R_M

输出

将答案打印为整数。


示例输入 1

5 3
5 4 6 2 3
4 1 2
7 2 4
14 2 5

示例输出 1

14

一个人可以获得以下至少一项 N = 5 书籍 14 日元如下。这是必须支付的最低费用。

  • 购买 1-st 设置为 B_1 = 4 日元获得 1-st 和 2-nd 书籍。
  • 购买 2-nd 设置为 B_2 = 7 日元获得 2-nd, 3-rd,和 4第本书。
  • 购买 5第本书 A_5 = 3 日元。

示例输入 2

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

示例输出 2

19