Thành phố đang tổ chức lễ hội pháo hoa. Khu vực lễ hội có địa điểm được đánh số từ đến trên một trục thẳng. Có màn bắn pháo hoa được lên lịch trình. Màn bắn thứ diễn ra tại thời điểm , tại vị trí , và mang lại độ vui vẻ cực đại là .
Nếu tại thời điểm , bạn đang đứng tại vị trí , độ vui vẻ bạn nhận được từ màn bắn thứ là . (Lưu ý: giá trị này có thể âm).
Bạn bắt đầu tại thời điểm ở bất kỳ vị trí nào bạn muốn. Mỗi đơn vị thời gian, bạn có thể di chuyển tối đa đơn vị khoảng cách (tức là từ có thể đến bất kỳ đâu trong đoạn ).
Hãy tìm lịch trình di chuyển sao cho tổng độ vui vẻ nhận được từ tất cả màn pháo hoa là lớn nhất.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên (, , ).
dòng tiếp theo, mỗi dòng chứa ba số nguyên (, , ).
Dữ liệu đảm bảo với mọi .
Kết quả:
In ra một số nguyên duy nhất là tổng độ vui vẻ lớn nhất có thể đạt được.
