Bài 4

Trong một chương trình nghệ thuật diễn ra liên tục trong $n$ giờ, Công ty $X$ có danh sách của $m$ 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ố theo thứ tự từ 1 tới $m$, nghệ sĩ thứ $i$ (với $i = 1, 2, \dots, m$) biểu diễn trong thời điểm $s_i$ đến thời điểm $t_i$ ($0 \le s_i < t_i \le n$) với tiền công là $c_i$ ($0 \le c_i \le 10^6$).

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 chi phí thuê là nhỏ nhất.

Đọc từ file CAU4.INP

• Dòng đầu tiên chứa 2 số nguyên $n$ và $m$ ($0 < n, m \le 100$)
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm $s_i$, $t_i$ và $c_i$, các số nằm trên một dòng và cách nhau một khoảng trắng.

Ghi ra file văn bản CAU4.OUT

• Một số nguyên là chi phí thuê nhỏ nhất (dữ liệu được cho đảm bảo luôn có kết quả).

• $0 < n, m \le 100$; $0 \le s_i < t_i \le n$; $0 \le c_i \le 10^6$.