510002 - 志愿者招募

【题目描述】志愿者招募（voluntee）

新项目需要招募一批短期志愿者。经过估算，这个项目需要n天才能完成，其中第i天至少需要ai个人，一共有m类志愿者可以招募。其中第i类可以从第si天工作到第ti天，招募费用是每人ci元。问如何用尽量少的费用招募足够的志愿者。

第一行包含两个整数n，m，表示完成项目的天数和可以招募的志愿者的种类。接下来的一行中包含n个非负整数，表示每天至少需要的志愿者人数。 接下来的m行中每行包含三个整数si，ti，ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

仅包含一个整数，表示你所设计的最优方案的总费用。

【数据范围】 1≤n≤1000，1≤m≤10000，题目中其它所涉及的数据均不超过$2^(31)−1。