EMPLOY Tuyển dụng

Một siêu thị cần tuyển một số nhân viên bán hàng. Giờ làm việc trong mỗi ngày được tính từ thời điểm tới thời điểm 0 đến thời điểm t ([0, t]). Có n ứng viên đánh số từ 1 tới n. Ứng viên thứ i chỉ có thể làm từ thời điểm a_i tới thời điểm b_i trong ngày ([a_i, b_i]) nếu được tuyển dụng và ứng viên đó yêu cầu mức lương mỗi ngày là c_i.

            Yêu cầu: Hãy giúp siêu thị tuyển một số nhân viên bán hàng trong số các ứng viên sao cho: Bất kỳ thời điểm nào trong giờ làm việc cũng có ít nhất một nhân viên bán hàng và tổng tiền lương phải trả trong mỗi ngày cho các nhân viên là ít nhất.

Input

• Dòng 1 chứa số nguyên dương n ≤ 10⁵ và số nguyên dương t ≤ 10⁹.
• N dòng tiếp theo, dòng thứ i chứa ba số nguyên a_i, b_i, c_i (0 ≤ a_i ≤ b_i ≤ t; 1 ≤ c_i ≤ 10⁹)

Output

• Dòng 1 ghi tổng tiền lương phải trả mỗi ngày cho các nhân viên theo phương án tìm được.
• Dòng 2 ghi chỉ số những ứng viên được chọn trong phương án tìm được theo thứ tự tùy ý.

Các số trên một dòng của input/output files được phải ghi cách nhau ít nhất một dấu cách Dữ liệu vào luôn đảm bảo tồn tại phương án tuyển dụng theo yêu cầu đặt ra Nếu có nhiều phương án cùng tối ưu, chỉ đưa ra một phương án

Input	Output
5 8 0 2 10 0 4 30 1 7 90 3 7 60 7 8 10	100 2 4 5

Giải thích: