Salesman

Điểm: 1,38 (OI)

Giới hạn thời gian: 3.6s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

IOI 2009, day 2

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một thương nhân vừa quyết định mua một con tàu mới phục vụ cho các cuộc trao đổi hàng hóa dọc bờ sông Danube. Con tàu của anh ta có tốc độ rất tuyệt vời, nó có thể đưa anh ta đến bất kì vị trí nào trên sông trong không quá một tích tắc, nhưng, đó lại là một con tàu rất tốn nhiên liệu. Con tàu tốn ~U~ dollar cho ~1~ mét đi ngược dòng, và mất ~D~ dollar cho ~1~ mét đi xuôi dòng.

Có tất cả ~N~ hội chợ sắp sửa diễn ra trên khắp bờ sông Danube. Mỗi hội chợ chỉ diễn ra trong ~1~ ngày. Với mỗi hội chợ ~x~, thương nhân biết hội chợ bắt đầu vào ngày ~T[x]~ (tính từ khi mua tàu), tại vị trí cách thượng nguồn ~L[x]~ mét, và nếu tham gia, thương nhân sẽ kiếm được ~M[x]~ dollar. Anh ta sẽ phải bắt đầu và kết thúc chuyến đi của mình tại một vị trí cách thượng nguồn ~S~ mét.

Lưu ý rằng, các hội chợ bắt đầu theo thứ tự thời gian, nên nếu như hội chợ ~A~ được bắt đầu sớm hơn hội chợ ~B~, thương nhân không thể tham gia hội chợ ~B~ trước hội chợ ~A~. Tuy nhiên, nếu như có nhiều hội chợ diễn ra trong cùng ~1~ ngày, thương nhân có thể tham gia bất kì hội chợ nào theo bất kì thứ tự nào anh ta muốn. Thương nhân có thể đi qua ~1~ hội chợ nhiều lần trong ngày, nhưng dĩ nhiên, anh ta sẽ chỉ kiếm được tiền trong lần đầu tiên ghé qua hội chợ đó.

Nhiệm vụ của bạn, là hãy viết chương trình giúp thương nhân tính được số tiền nhiều nhất thu được, khi tham gia các hội chợ theo phương án tối ưu. Số tiền kiếm được, bằng tổng lợi nhuận đạt được từ những hội chợ anh ta tham gia, trừ đi chi phí di chuyển trên sông.

Input

Dòng đầu tiên gồm ~4~ số nguyên ~N~, ~U~, ~D~, ~S~
~N~ dòng tiếp theo, mỗi gồm ~3~ số ~T[k]~, ~L[k]~, ~M[k]~ mô tả hội chợ ~k~: hội chợ bắt đầu vào ngày ~T[k]~, cách thượng nguồn ~L[k]~ mét, và lợi nhuận đạt được nếu tham gia là ~M[k]~

Các số trên cùng ~1~ dòng cách nhau bởi ít nhất ~1~ dấu cách

Output

Gồm ~1~ số nguyên duy nhất, là số tiền lớn nhất mà thương nhân có thể kiếm được (giá trị này có thể bằng ~0)~.

Giới hạn

~1 \le N \le 500000~, số hội chợ
~1 \le D \le U \le 10~, chi phí di chuyển ~1~ mét ngược dòng ~(U)~, và xuôi dòng ~(D)~
~1 \le S \le 500001~, vị trí xuất phát của thương nhân
~1 \le~ ~T[k]~ ~\le 500000~, ngày diễn ra hội chợ thứ ~k~
~1 \le~ ~L[k]~ ~\le 500001~, vị trí của hội chợ thứ ~k~
~1 \le~ ~M[k]~ ~\le 4000~, số tiền thương nhân có thể kiếm được nếu tham gia hội chợ thứ ~k~
Không có hai hội chợ nào được mở ở cùng vị trí, cũng như không có hội chợ nào được mở tại nhà của thương nhân

Sample Input

Sample Output

Note

Phương án tối ưu của thương nhân sẽ là tham gia hội chợ ~1~ và ~3~, theo thứ tự như sau

Đi ngược dòng ~20~ mét, chi phí ~100~ dollar. Lợi nhuận hiện tại: ~-100~
Tham gia hội chợ ~1~, kiếm được ~100~ dollar. Lợi nhuận hiện tại: ~0~
Đi ngược dòng ~5~ mét, chi phí ~25~ dollar. Lợi nhuận hiện tại: ~-25~
Tham gia hội chợ ~3~, kiếm được ~150~ dollar. Lợi nhuận hiện tại: ~125~
Đi xuôi dòng ~25~ mét và trở về nhà, chi phí ~75~ dollar. Lợi nhuận cuối cùng: ~50~ dollar

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.