AT_past202209_m シリーズ

有一个漫画系列，一共包含 $N$ 本书。第 $i$ 本（$1 \leq i \leq N$）书售价为 $A_i$ 日元。 这些书也可以成套出售。共有 $M$ 套，第 $j$ 套（$1 \leq j \leq M$）售价为 $B_j$ 日元，包含了该系列中的第 $L_j$ 本到第 $R_j$ 本书（即 $L_j$、$L_j + 1$、$\ldots$、$R_j$）。 要获得每一种书至少一本，至少需要支付多少日元？

输入从标准输入中读取，格式如下： > $N$ $M$ > $A_1$ $A_2$ $\ldots$ $A_N$ > $B_1$ $L_1$ $R_1$ > $\vdots$ > $B_M$ $L_M$ $R_M$

输出一个整数，表示获得每一种书至少一本所需支付的最小日元数。

### 样例解释 1 要以最少的花费获得每本书各至少一本（$N=5$），方式如下，一共需要 $14$ 日元，这就是所需的最小金额。 - 以 $B_1 = 4$ 日元购买第 $1$ 套，可得到第 $1$ 本和第 $2$ 本书。 - 以 $B_2 = 7$ 日元购买第 $2$ 套，可得到第 $2$ 本、第 $3$ 本和第 $4$ 本书。 - 以 $A_5 = 3$ 日元购买第 $5$ 本书。 # 限制 - $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)$ - 输入中的所有值均为整数。 由 ChatGPT 5 翻译