Giải bài trực tuyến

Tiếp theo chiến lược “quy hoạch động”, Bờm huấn luyện cho chú chó của mình chiến lược “tham ăn” trong một sân chơi được biểu diễn bởi mặt phẳng trực chuẩn . Ban đầu chú chó xuất phát ở điểm (0,0) và nó phải đứng im cho tới khi được gọi. Trò chơi diễn ra trong N lượt, lượt thứ i của trò chơi diễn ra như sau:

Bờm di chuyển đến vị trí (x_i,y_i), cầm c_i cái bánh và gọi chú chó. Chú chó có quyền đứng im hoặc di chuyển theo các phương song song theo trục tọa độ để đến chỗ Bờm nếu độ dài quãng đường di chuyển không vượt quá K. Nếu chú chó có thể đi được đến chỗ Bờm và quyết định di chuyển, nó sẽ được thưởng toàn bộ c_i cái bánh, ngược lại nó sẽ phải đứng nhìn Bờm ăn hết luôn c_i cái bánh đó. Hết lượt chơi này chú chó lại phải đứng im và trò chơi tiếp tục ở lượt i+1.

Yêu cầu: Cho biết trước các tọa độ (x_i,y_i) và số bánh c_i tại các lượt chơi, hãy giúp chú chó tội nghiệp của Bờm kiếm được nhiều bánh nhất

Input

• Dòng 1 chứa hai số nguyên dương N,K.
• N dòng tiếp theo, dòng thứ  chứa ba số nguyên dương x_i,y_i,c_i.

Ràng buộc: N<=10⁵, tất cả các số còn lại trong file dữ liệu đều là số nguyên dương <=10³.

Output

• Gồm một số nguyên duy nhất là số bánh chú chó kiếm được trong trò chơi theo phương án của bạn.

Example

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

Output:

27

Giải thích: đây là ví dụ với 8 lượt chơi và vị trí của Bờm tại 8 lượt chơi đó lần lượt là A, B, C, D, E, F, G, H. Trong phương án tối ưu chú chó chỉ phải bỏ 9 bánh tại điểm B và 8 bánh tại điểm E.