A - 志愿者招募.md

A : 志愿者招募

Time Limit: 1 Sec, Memory Limit: 128 Mb

Description

奥运将至，布布需要为奥运项目招募一批短期志愿者。经过估算，这个项目需要 n 天才能完成，其中第 i 天至少需要 $a_i$ 个志愿者。布布通过了解得知，一共有 m 类志愿者可以抬募。其中第 i 类可以从第 $s_i$ 天工作到$t_i$天，招募费用是每人$c_i$ 元。布布希望用尽量少的费用招足够多的志愿者，请你帮他设计一种最优的招募方案。

Input

第一行包含两个整数 n, m, 表示完成项目的天数和可以招募的志愿者的种类数。(1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000)

接下来的一行中包含 n 个非负整数，表示各天至少需要的志愿者人数。

接下来的 m 行中每行包含三个整数 $s_i$, $t_i$, $c_i$, 含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的，同时保证一定存在最优方案。($1\leq s_i\leq t_i\leq n$,  $c_i\leq2^{31}-1$)

Output

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

Sample Input

3 3
2 3 4
1 2 2
2 3 5
3 3 2

Sample Output

14

参考代码