提示: 欢迎访问OurACM平台。
Problem 2079 最大获利

Accept: 36    Submit: 279
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

Sean准备投资一些项目。有n个投资项目,投资第i个项目需要花费Ci元。Sean发现如果投资了某些编号连续的项目就能赚得一定的钱。现在给出m组连续的项目和每组能赚得的钱,请问采取最优的投资策略的最大获利是多少?

样例最佳策略是全部项目都投资,然后第1,2组都满足了,获利为2+2-3=1。最佳策略可能是不投资,即最大获利为0。

Input

每组数据第一行输入两个整数N和M , N表示项目数,M表示能获利的连续的项目组数,1 <= N <= 20000,1 <= M <= 20000 , 接下来一行输入N个数,表示每个项目投资需要的花费Ci,1<=Ci<=10^9。

接下来m行,每行3个数Li,Ri,Pi,1<=Li<=Ri<=N,1<=Pi<=10^9,表示投资从第Li到第Ri这些连续的项目的获利。每组连续投资的获利互不影响,如果投资的多组连续投资都包含项目i,项目i只需要投资一次。

Output

对于每组数据输出一行,即最大获利。

Sample Input

3 2 1 1 1 1 2 2 2 3 2

Sample Output

1

Source

FOJ有奖月赛-2012年4月(校赛热身赛)

Submit  Back  Status  Discuss