Một dải băng hình chữ nhật kích thước 1 ×M được chia thành M ô vuông. Các ô được đánh số từ 1 đến M theo thứ tự từ trái sang phải. Ban đầu, các ô của dải băng đều có màu trắng.

Có N thao tác tô màu có thể thực hiện trên dải băng, thao tác thứ i tô màu đen cho các ô từ vị trí l[i] đến vị trí r[i]. Việc thực hiện thao tác thứ i sẽ mang lại điểm số si. Mỗi thao tác chỉ được thực hiện tối đa một lần.

Người chơi sẽ chọn một số thao tác tô màu và lần lượt thực hiện các thao tác đó. Điểm số của người chơi sẽ bằng tổng số điểm của các thao tác được chọn. Tuy nhiên, sau khi thực hiện các thao tác được chọn, nếu tất cả các ô đều được tô màu đen thì người chơi sẽ thua cuộc và điểm số sẽ là 0.

Hãy cho biết điểm số tối đa có thể đạt được.

Input

• Dòng đầu tiên gồm hai số nguyên N và M (1 ≤ N, M ≤ 200000) - số thao tác và số ô của dải băng.

• N dòng tiếp theo, dòng thứ i gồm ba số nguyên li, ri và si (1 ≤ li ≤ ri ≤ M, si ≤ 5000) -mô tả thao tác thứ i.

Output

Ghi ra điểm số tối đa có thể đạt được.

Sample Input

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

Sample Output

8

Sample Input

3 3
1 1 5
1 1 5
1 3 100

Sample Output

10

Giải thích

• Ở ví dụ thứ nhất, ta sẽ thực hiện các thao tác 1, 3 và 4, khi đó còn hai ô vuông không được
tô màu đen là 5 và 8. Tổng điểm số sẽ là 4 + 2 + 2 = 8.
Ở ví dụ thứ hai, ta sẽ thực hiện các thao tác 1 và 2 (hai thao tác này vẫn được xem là khác
nhau). Tổng điểm số sẽ là 5 + 5 = 10.

Giới hạn:

• Subtask 1 (30% số test): N, M ≤ 18
• Subtask 2 (30% số test): N, M ≤ 5000
• Subtask 3 (40% số test): Không có ràng buộc gì thêm