Billboard painting

View as PDF

Submit solution

Points: 0.67 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Prof. Nguyen Duc Nghia
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 ~1*N~ được chia ra làm ~N~ vạch kích thước ~1*1~. Các vạch được đánh số từ trái sang phải bắt đầu từ ~1~. Thợ ~i~ ~(1 \leq i \leq K)~ đang ngồi trước vạch ~S_{i}~ 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 ~S_{i}~. Thợ ~i~ chỉ có thể sơn không quá ~L_{i}~ vạch và tiền công mà anh ta nhận được từ việc sơn một vạch là ~P_{i}~. 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.

Input

  • Dòng đầu tiên chứa hai số nguyên dương ~N~, ~K~ ~(N \leq 16000~; ~K \leq 100)~.
  • Dòng thứ ~i~ trong số ~K~ dòng tiếp theo chứa ba số nguyên ~L_{i}~, ~P_{i}~, ~S_{i}~ ~(i = 1~, ~2~, ...~K)~ được ghi cách nhau bởi dấu cách ~(1 \leq P_{i} \leq 10000~, ~1 \leq L_{i}~, ~S_{i} \leq 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 ~S_{i}~ có thể được phân công cho thợ khác.
  • Các số ~S_{1}~, ~S_{2}~, ...~S_{K}~ giả thiết là khác nhau từng đôi.

Output

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

Sample Input

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

Sample Output

17

Note

(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).


Comments

Please read the guidelines before commenting.


There are no comments at the moment.