NKPANO - Billboard painting

A group of K painters has to paint a rectangular billboard of size 1xN. The billboard is divided into N cells of size 1x1. The cells are numbered from 1 to N in left to right order.

The i-th painter (1 ≤ i ≤ K) is currently standing in front of the cell Si. He either can paint no cells at all or can paint a consecutive number of cells that must containt the cell Si. Moreover, he can only paint at most Li cells, and for each painted cell, he will receive a payment of Pi dollars. Each cell can be painted by at most one person.

Your task is to find a way for the painters to receive the largest amount of payment.

Input

  • The first line of the input contains two positive integers N, K (N ≤ 16000; K ≤ 100).
  • The i-th line of the next K lines contains three positive integers Li , Pi, Si (i = 1, 2, … K) separated by spaces (1 ≤ Pi ≤ 10000, 1 ≤ Li , Si ≤ N ). The numbers S1, S2, . . . SK are pairwise distinct.

Output

A single line contains the largest payment that the painters can receive.

Example

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

Output
17

The first painter will paint the first two cells, the second painter will paint the next two cells, the third one will paint the remaining cells and the last won't have to paint any cells.


Added by:Jimmy
Date:2008-01-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET
Resource:Prof. Nguyen Duc Nghia

hide comments
2013-09-01 15:43:43 Ruslan Osmanov
I wonder why my rank is 10?
MEM=0k, TIME=0.00s. The only attempt succeded. And yes, what does RESULT = 0 mean?
2011-06-10 14:32:27 MAT
vsem uda4i
2010-12-22 16:56:15 Ashish
@erel the third one will paint all the remaining but one. The last cell will be left unpainted as mentioned clearly in the question.
2010-11-04 13:06:21 Erel Segal
"the third one will paint the remaining cells" - but, if I read correctly, L3=3, and there are 4 cells remaining!

Maybe the first line of input should read:
7 4
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.