SP2899 VOL - Volunteers

ACM ICPC 2009 年世界总决赛将在瑞典斯德哥尔摩举行，由 IBM 赞助并由瑞典皇家理工学院（KTH）承办。这场比赛将持续 $N$ 天（$1 \le N \le 1000$）。在比赛的第 $i$ 天，我们需要至少 $A_i$ 名志愿者协助工作。目前我们可以选择 $M$ 类志愿者（$1 \le M \le 10000$），其中第 $i$ 类志愿者能够从第 $S_i$ 天工作到第 $T_i$ 天，他们的服务费用为 $C_i$。你需要做的是合理选择雇佣方案，确保所有天数的志愿者需求都能满足，并使总花费最小化。

共有十组测试数据（需要依次处理每一组）。对于每组测试数据： - 第一行包含两个整数 $N$ 和 $M$，表示比赛天数和志愿者类型数。 - 第二行包含 $N$ 个非负整数 $A_i$，表示每天需要的志愿者数量。 - 随后的 $M$ 行中，每行包含三个整数 $S_i$、$T_i$ 和 $C_i$，表示志愿者类型的工作时段起始天、结束天和每日费用。 提示：计算中使用 C/C++/Java 的 **int** 或 Pascal 的 **longint** 类型即可。

对每组测试数据： 输出一行，表示满足所有志愿者需求的最小花费。 **本翻译由 AI 自动生成**