Hè năm nay công ty lữ hành MK mở ra ~n~ tour du lịch, tour thứ ~i~ (1 ~\leq~ ~i~ ~\leq~ ~n~) bắt đầu từ thời điểm ~s_i~ và kết thúc vào ~f_i~ với chi phí là ~c_i~ (1 ~\leq~ ~c_i~ ~\leq~ ~10^9~ , như vậy số giờ tham quan của tour này là ~f_i~ - ~s_i~ + 1 . Du khách có thể tham gia nhiều tour khác nhau nếu như các tour đó có thời điểm diễn ra không bị giao nhau (tour ~i~ và ~j~ không bị giao nhau nếu ~f_i~ < ~s_j~ hoặc~f_j~ < ~s_i~ ).

Nga muốn chọn tham gia hai tour khác nhau sao cho tổng số số giờ tham quan đúng bằng ~m~ và tổng chi phí của hai tour được chọn là ít nhất.

Yêu cầu: Tính chi phí ít nhất của hai tua Nga có thể chọn được theo yêu cầu.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên dương ~n~ và ~m~ (2 ~\leq~ ~n,m~ ~\leq~ ~2~x~10^5~ ) ;
• ~n~ dòng tiếp theo, dòng thứ ~i~ ghi 3 số lần lượt là ~s_i~, ~f_i~, ~c_i~ (1 ~\leq~ ~s_i~ ~\leq~ ~f_i~ ~\leq~ ~2~x~10^5~ );
• Các số trong tệp cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra chi phí ít nhất có thể chọn được, nếu không thể chọn ghi ra ~-1~

Ví dụ:

Input

3 3
11 11 2
3 4 3
8 9 2

Output

4

Ràng buộc:

• Có 30% test ~n~ ~\leq~ 20 tương ứng với 30% số điểm
• Có 30% test 20 < ~n~ ~\leq~ 1000 tương ứng với 30% số điểm
• Có 40% test không ràng buộc gì thêm