Một công ty cung cấp dịch vụ cho thuê kho chứa hàng. Công ty nhận được n đơn đặt thuê kho hàng của khách hàng \(1, . . . , n,\) mỗi đơn thuê của khách hàng \(i\) sẽ bao gồm:

• \(s_i\): ngày bắt đầu thuê
• \(d_i\): số ngày cần thuê
• \(r_i\): số tiền khách hàng \(i\) thuê phải trả cho công ty.

Tại mỗi thời điểm, kho hàng của công ty chỉ có thể phục vụ cho \(1\) đơn thuê duy nhất, đồng thời khi một khách hàng kết thúc sử dụng kho hàng thì công ty cần có \(K\) ngày để bảo trì kho trước khi cho một khách hàng khác thuê: cụ thể, khách thứ nhất kết thúc thuê vào ngày thứ \(x\) thì khách thứ hai chỉ có thể thuê sau ngày thứ \(x + K\). Hãy giúp công ty lựa chọn các khách để cho thuê sao cho tổng số tiền thu được là lớn nhất.

Dữ liệu vào

• Dữ liệu đầu vào bao gồm các dòng sau:
• Dòng \(1\): ghi \(2\) số nguyên dương \(n,K\) \((1 ≤ n ≤ 10^6, 1 ≤ K ≤ 10^9) \)
• Dòng thứ \(i + 1(i = 1, . . . , n)\): ghi \(3\) số nguyên dương \(s_i, d_i, r_i (1 ≤ s_i, d_i, r_i ≤ 10^9)\)

Dữ liệu ra

• Tổng số tiền lớn nhất thu được.

Input 1

5 2 
8 3 9 
5 1 7 
9 2 6 
4 3 8 
1 2 5

Output 1

21

Giải thích

Công ty sẽ lựa chọn 3 khách cho thuê là khách thứ ~1, 2,~ và ~5~ với tổng số tiền thu được là ~9 + 7 + 5= 21~.

Hạn chế

• 30% số điểm có \(n,K ≤ 10 \)
• 20% số điểm có \(n ≤ 10^4,K ≤ 10, s_i ≤ 10^4, d_i ≤ 100, r_i ≤ 10^3 \)
• 30% số điểm có \(n,K, s_i, d_i, r_i ≤ 5 × 10^4\)
• 20% số điểm còn lại không có ràng buộc gì thêm