题目描述

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要n天才能完成，其中第i天至少需要$a_i$个人。布布通过了解得知，一共有m类志愿者可以招募。其中第i类可以从第$s_i$天工作到第$t_i$天，招募费用是每人$c_i$元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

输入格式

第一行包括两个整数n,m，表示完成项目的天数和可以招募的志愿者的种类。

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

接下来m行，每行三个整数$s_i$,$t_i$,$c_i$，含义如上文所述。

为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

输出格式

输出一个整数，表示你所设计的最优方案的总费用

样例输入

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

样例输出

14

提示

招募3名第一类志愿者和4名第三类志愿者。

对于30%的数据，$1\le N,M\le 10,1\le a_i\le 10$

对于100%的数据，$1\le N\le 1000,1\le M\le 10000$，题目中所涉及的数据均不超过$2^{31}-1$。

1 1
0
1 1 1928689793

0

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

14

8 8
3 8 7 8 8 4 5 5 
2 3 904
1 3 145
2 3 678
1 2 899
5 5 618
1 4 756
5 8 930
1 1 435

12552