刷木板

题目描述:

K个人对N块从左到右编号是1到N的木板进行粉刷，每个人初始站在一块木板前（不重复），每人最多只能涂包含所站木板的连续L个木板或一个木板也不粉刷。给出每人最多粉刷的木块数L，粉刷一快木板的工钱p，站的木板s。求这群人最多共获得多少工钱。

输入格式:

N K 
L1 P1 S1 
L2 P2 S2 
... 
LK PK SK 

解释：

N -木板数量; K -工人的数目 
Li -第i个工人能粉刷的最长的木板数
Pi -第i个工人每粉刷一块木板的收益
Si -第i个工人所站的木板编号

输出格式:

一个整数，表示所有工作的最大收益值。

样例输入:

8 4
3 2 2
3 2 3
3 3 5
1 1 7 

样例输出:

17

提示:

the worker 1 刷的木板是 [1, 2]; 

the worker 2 刷的木板是[3, 4]; 

the worker 3 刷的木板是 [5, 7]; 

the worker 4 什么都不做

1 <= N <= 16 000，1 <= K <= 100，1 <= Pi <= 10 000

时间限制: 1000ms
空间限制: 256MB

---