NKPANO - Billboard painting
English | Vietnamese |
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 S_{i}. He either can paint no cells at all or can paint a consecutive number of cells that must containt the cell S_{i}. Moreover, he can only paint at most L_{i} cells, and for each painted cell, he will receive a payment of P_{i} 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 L_{i }, P_{i}, S_{i} (i = 1, 2, … K) separated by spaces (1 ≤ P_{i} ≤ 10000, 1 ≤ L_{i} , S_{i} ≤ N ). The numbers S_{1}, S_{2}, . . . S_{K} 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.
hide comments
Piotr:
2011-06-10 17:57:57
I don't get the example. If the first two painters paint two cells each, total four, and third can paint a maximum of three cells, the total is seven, while there are eight cells to paint. Unless I miss something obvious, given example is unsolvable... Last edit: 2011-06-10 17:58:46 |
Added by: | Duc |
Date: | 2008-01-13 |
Time limit: | 0.159s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Prof. Nguyen Duc Nghia |