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 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ố thứ tự từ 1 đến m, nghệ sĩ thứ i biểu diễn trong thời điểm s_i đến thời điểm
t_i (0 <= s_i < t_i <= n) với tiền công là c_i (0 <= c_i <= 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 tổng chi phí thuê là nhỏ nhất.

Dữ liệu: Vào từ file VANNGHE.INP gồm:

• Dòng đầu tiên chứa 2 số nguyên dương n, m (1 <= n, m <= 400).
  

• m dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm s_i, t_i, c_i.
  

Kết quả: Ghi ra file VANNGHE.OUT

Một số nguyên duy nhất là chi phí thuê nhỏ nhất. Nếu không có phương án thuê thỏa mãn, ghi -1.

Ví dụ:

VANNGHE.INP
9 5
0 5 25
1 3 18
3 7 21
4 6 38
7 9 20

VANNGHE.OUT
66

Giải thích:

Ta chọn các nghệ sĩ: (0, 5) giá 25, (3, 7) giá 21, và (7, 9) giá 20.

Tổng chi phí: 25 + 21 + 20 = 66.

Các khoảng thời gian được phủ kín từ 0 đến 9: [0, 5] hợp với [3, 7] hợp với [7, 9] = [0, 9].