OpenJudge

0012:招募志愿者

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
65536kB
描述

第十二届全国运动会将于明年在辽宁省举办,在办会期间都要招募大量的志愿者协助会务工作,组委会对运动会已经开始筹备,即将开展志愿者的招募工作。经过估算,整个会期需要N天才能完成,其中第i天至少需要Ai个人。一共需要招募M类志愿者,其中第i类可以从第Bi天工作到第Ei天,招募费用是支付志愿者每人报酬Ci元。组委会希望用尽量少的费用招募到足够的志愿者,请你帮他们设计一种最优的招聘方案。

输入
输入文件volunteer.in的第一行包含两个整数N,M,表示完成项目的天数和可以招聘的志愿者的种类。
接下来的一行中包含N个非负整数,表示每天至少需要的志愿者人数。
接下来的M行中每行包含三个整数Bi,Ei,Ci,含义如题所示。为了方便起见,我们可以认为每类志愿者的数量都是无限多的。
输出
输出文件volunteer.out中仅包含一个整数,表示你所设计的最优方案的总费用。
样例输入
3 3 
5 6 9
1 2 10
2 3 25
3 3 10
样例输出
150
提示
样例为招募第6名第一类志愿者和9名第三类志愿者
30%的数据中,1<=N,M<=10,1<=Ai<=10;
100%的数据中,1<=N<=1000,1<=M<=10000,题目中其他涉及的数据均不超过2的31次方减1
全局题号
4849
添加于
2012-05-22
提交次数
9
尝试人数
3
通过人数
3