### 问题描述 你是一名顶级算法工程师，刚刚参加了一家互联网药企的面试，很快优秀的你便从众多求职者中脱颖而出拿下 offer。 面试结束时，CEO 透露了公司当前面临的一个棘手问题，这让你心中一震。这个问题不仅关系到公司的利润，更直接影响到无数患者的用药成本。CEO 眼中闪烁着期待的光芒，郑重地告诉你：“如果你能解决这个药品价格优化的问题，我将让你成为此项目的 leader！” 具体地：公司的网站总共销售 $N$ 种药物，每种药物的单瓶价格为 $S_i$。同时，公司作为售卖机构，与药品生产方之间有多种合作方案。总共有 $M$ 种合作售卖方案，第 $i$ 种方案允许患者同时购买第 $A_i$ 种药物到第 $B_i$ 种药物的各一瓶（包括 $A_i$ 和 $B_i$），且购买总价格为 $C_i$。 你的任务是设计一个高效的算法，帮助用户计算出购买每种药物**至少**一瓶的最低总价，进而实现价格优化。 ### 输入格式 第一行输入两个整数 $N,M( 1\leq N,M \leq 10^5)$ 表示药物种类数以及合作售卖方案数。 第二行输入 $N$ 个整数 $S_1,S_2,S_3,\cdots,S_n(1 \leq S_i \le 10^6)$ 表示第 $i$ 种药物的价格。 接下来 $M$ 行，每行三个整数 $A_i,B_i,C_i(1 \leq A_i \leq B_i \le N,1 \leq C_i \leq 10^6)$ 表示一种合作售卖方案。 ### 输出格式 输出一个整数表示答案。 ### 样例输入 ```text 5 3 1 10 3 7 9 1 3 4 2 5 20 4 5 13 ``` ### 样例输出 ```text 17 ```