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.|

BARICAVN - BARICA

Barica là một con cóc không bình thường. Barica sống trong một cái ao, nơi có N lá sen bềnh bồng trên mặt nước. Những lá sen được đánh số từ 1 đến N. Nhìn từ trên xuống, mỗi lá sen đc xem như một điểm trên hệ trục tọa độ Oxy. Barica có thể nhảy từ lá sen có tọa độ (x1;y1) đến tọa độ (x2,y2) nếu:

_ x2 > x1 và y1 = y2 hoặc
_ y2 > y1 và x1 = x2

Với mỗi lá sen, chúng ta biết được số lượng ruồi gần đó. Barica có thể dùng lưỡi tóm gọn tất cả những con ruồi gần lá sen mà nó đang đứng.

Barica thu được một đơn vị năng lượng với mỗi con ruồi mà nó bắt được và mất K đơn vị năng lượng cho mỗi bước nhảy từ lá sen này sang lá sen khác. Barica không thể thực hiện cú nhảy nếu năng lượng hiện tại của nó nhỏ hơn K.

Barica muốn đi từ lá sen 1 đến lá sen N và tích trữ được nhiều năng lượng nhất có thể khi đang ở lá sen N. Năng lượng của Barica ban đầu bằng 0 và dĩ nhiên nó phải lấy năng lượng từ lá sen 1 để thực hiện cú nhảy.
Hãy tìm năng lượng lớn nhất mà Barica có thể có được tại lá sen N.

Input

_ Dòng đầu là số N và K (N<=300 000; K<=1000) cách nhau bởi khoảng trắng
_ N dòng sau mỗi dòng chứa 3 số x_i, y_i, F_i với x_i và y_i là tọa độ lá sen thứ i và F_i là số ruồi ở lá sen i. (0 <= x_i, y_i <= 100 000; 0 <= F_i <=1000)
Lưu ý: không có hai lá sen nào trùng tọa độ và luôn tồn tại ít nhất một đường đi từ 1 tới N.

Output

_ Một dòng duy nhất là năng lượng cao nhất mà Barica có thể có được khi kết thúc ở lá sen thứ N.

Example

Input:
6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 5


Output:
5

Được gửi lên bởi:PNL
Ngày:2009-04-24
Thời gian chạy:0.200s
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ừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COCI 2007-2008

hide comments
2016-09-27 03:02:44
Code AC:
http://shink.in/Qu8tS
2016-02-29 15:58:35
Tham khảo tại : http://phuotvnspoj.blogspot.com/2016/02/baricavn-barica.html
2015-10-27 19:46:15
Blog Thuật toán SPOJ hy vọng giúp được cho mọi người : http://www.oni.vn/uR57W
2015-10-20 10:55:47
hy vọng giúp được cho mọi người : http://www.oni.vn/uR57W
2015-10-08 09:15:26
sol : http://www.oni.vn/a9oHZ
code : http://www.oni.vn/7nxXf
2015-08-14 16:42:46 ChienTran
mất 1 đấm vì sort dùng random mà quên randomize :3
2015-07-26 19:58:10 there's no salvation for me...
mất 1 đấm vì sai sort =)))
2015-03-19 17:40:45 CK
Nếu để ý trước comment của [KC]★★★★*-RAMEN thì đã ko mất 1 đấm AC :(. Tks bạn này nhiều nếu ko cũng ko biết sai chỗ nào
2014-10-05 05:03:55 [KC]★★★★*-RAMEN
đi từ lá bèo thứ nhất lúc chưa sort nhá các bác
2014-04-12 18:54:01 Lollipop
n lúc dầu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.