Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SMARTDOG - Tham ăn

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/smartdog


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í (xi,yi), cầm ci 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ộ ci cái bánh, ngược lại nó sẽ phải đứng nhìn Bờm ăn hết luôn ci 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 độ (xi,yi) và số bánh ci 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 xi,yi,ci.

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

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.


Được gửi lên bởi:VOJ Team
Ngày:2011-08-05
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VNOI Marathon 2011 - Problem Setter: Lê Minh Hoàng

hide comments
2011-08-09 10:15:00 Noyethug


Last edit: 2011-11-13 12:21:00
2011-08-09 03:09:40 1212


Last edit: 2011-08-09 06:21:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.