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 ~\left(0,0\right)~ 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í ~\left(x_{i}, y_{i}\right)~, 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 độ ~\left(x_{i}, y_{i}\right)~ 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ứ ~i~ chứa ba số nguyên dương ~x_{i}~, ~y_{i}~, ~c_{i}~.

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.

Giới hạn

~N \le 10^{5}~, tất cả các số còn lại trong file dữ liệu đều là số nguyên dương ~\le 10^{3}~.

Sample 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

Sample Output

27

Note

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.