分数: 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