有一个漫画系列，一共包含 $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 翻译