Mô tả và yêu cầu

Trong một chương trình nghệ thuật diễn ra liên tục trong 𝑛 giờ, công ty X có
danh sách 𝑚 nghệ sĩ khác nhau có thể thuê để biểu diễn. Thời điểm bắt đầu biểu diễn
được tính bằng 0 . Để đơn giản trong quản lý và sắp xếp, các nghệ sĩ được đánh số
thứ tự từ 1 đến 𝑚, nghệ sĩ thứ 𝑖(𝑖 = 1,2, … , 𝑚) biểu diễn trong thời điểm 𝑠𝑖 đến thời
điểm 𝑡𝑖 (0 ≤ 𝑠𝑖 < 𝑡𝑖 ≤ 𝑛) với tiền công là 𝑐𝑖(0 ≤ 𝑐𝑖 ≤ 106).

Yêu cầu: Viết chương trình thuê các ngh ệ sĩ để bất cứ thời điểm nào cũng luôn
có ít nhất một nghệ sĩ biểu diễn đồng thời tổng chi phí thuê là nhỏ nhất.
Dữ liệu: vào từ thiết bị nhập chuẩn gồm:
 Dòng đầu tiền chứa 2 số nguyên dương 𝑛,𝑚(1 ≤ 𝑛,𝑚 ≤ 400).
 𝑚 dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm 𝑠𝑖, 𝑡𝑖,𝑐𝑖.
Kết quả: ghi ra thiết bị xuất chuẩn chứa một số nguyên là chi phí thuê nhỏ
nhất.

Ví dụ

INPUT                         OUTPUT
                  9 5                               66
                  0 5 25
                  1 3 18
                  3 7 21
                  4 6 38
                  7 9 20