NKPANO - Billboard painting

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkpano


Một đội thợ sơn gồm K người cần thực hiện sơn một bức pano dành cho quảng cáo có dạng một hình chữ nhật kích thước 1xN được chia ra làm N vạch kích thước 1x1. Các vạch được đánh số từ trái sang phải bắt đầu từ 1. Thợ i (1 ≤ i ≤ K) đang ngồi trước vạch Si của pano và anh ta chỉ có thể sơn một dãy các vạch liên tiếp của pano trong đó phải có vạch Si. Thợ i chỉ có thể sơn không quá Li vạch và tiền công mà anh ta nhận được từ việc sơn một vạch là Pi . Mỗi vạch được sơn bởi không quá một thợ.

Yêu cầu: Tìm cách phân công thợ sơn các vạch của pano sao cho tổng tiền công của tất cả các thợ nhận được là lớn nhất.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên dương N, K (N ≤ 16000; K ≤ 100).
  • Dòng thứ i trong số K dòng tiếp theo chứa ba số nguyên Li , Pi, Si (i = 1, 2, … K) được ghi cách nhau bởi dấu cách (1 ≤ Pi ≤ 10000, 1 ≤ Li , Si ≤ N ).

Chú ý:

  • Cách phân công tìm được không nhất thiết phải đảm bảo sơn hết tất cả các vạch của pano.
  • Nếu thợ i không sơn vạch nào cả thì việc sơn vạch Si có thể được phân công cho thợ khác.
  • Các số S1, S2, . . . SK giả thiết là khác nhau từng đôi.

Kết quả

Ghi ra tổng tiền công nhận được từ cách phân công thợ tìm được.

Ví dụ

Dữ liệu:
8 4
3 2 2
3 2 3
3 3 5
1 1 7  

Kết qủa
17

(Cách phân công: Thợ 1 sơn các vạch 1, 2; thợ 2 sơn các vạch 3, 4; thợ 3 sơn các vạch 5, 6, 7; thợ 4 không sơn vạch nào).


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 VB.NET
Resource:Prof. Nguyen Duc Nghia

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.