Một người bán hàng lưu động nhận thấy việc lập lịch trình tối ưu cho các chuyến đi trên đất liền là một bài toán tính toán quá khó, nên quyết định chuyển việc kinh doanh sang thế giới một chiều của sông Danube. Ông có một chiếc thuyền rất nhanh, có thể đi từ bất kỳ điểm nào đến bất kỳ điểm nào khác trên sông mà không mất thời gian, nhưng tiếc là thuyền tiêu tốn rất nhiều nhiên liệu. Mỗi mét đi ngược dòng, tức hướng về đầu nguồn, tốn \(U\) đô la; mỗi mét đi xuôi dòng, tức ra xa đầu nguồn, tốn \(D\) đô la.

Có \(N\) hội chợ dọc theo sông mà người bán hàng muốn tham dự. Mỗi hội chợ chỉ diễn ra trong một ngày. Với mỗi hội chợ \(X\), ông biết ngày tổ chức \(T_X\), tính bằng số ngày kể từ khi mua thuyền; vị trí \(L_X\), tính bằng khoảng cách theo mét từ đầu nguồn xuôi theo dòng sông tới hội chợ; và số tiền \(M_X\) đô la mà ông sẽ thu được nếu tham dự. Hành trình của ông phải bắt đầu và kết thúc tại ngôi nhà bên sông của mình, ở vị trí \(S\), cũng được đo bằng số mét từ đầu nguồn theo chiều xuôi dòng.

Hãy giúp người bán hàng chọn những hội chợ cần tham dự, hoặc không tham dự hội chợ nào, và thứ tự tham dự để lợi nhuận khi kết thúc hành trình là lớn nhất. Tổng lợi nhuận bằng tổng số đô la thu được từ các hội chợ đã tham dự, trừ tổng số đô la chi cho việc đi lại ngược và xuôi dòng.

Lưu ý rằng nếu hội chợ \(A\) diễn ra trước hội chợ \(B\), người bán hàng chỉ có thể tham dự cả hai theo thứ tự \(A\) rồi \(B\), không thể tham dự \(B\) rồi mới đến \(A\). Tuy nhiên, nếu hai hội chợ diễn ra cùng ngày, ông có thể tham dự cả hai theo thứ tự bất kỳ. Không có giới hạn về số hội chợ có thể tham dự trong một ngày, nhưng không thể tham dự lại cùng một hội chợ để nhận tiền lần thứ hai. Ông có thể đi qua những hội chợ đã tham dự, nhưng không nhận thêm tiền.

Cho ngày tổ chức, vị trí và số tiền thu được của tất cả các hội chợ, cùng vị trí nhà và chi phí đi lại, hãy viết chương trình xác định lợi nhuận lớn nhất có thể đạt được khi kết thúc hành trình.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa bốn số nguyên \(N\), \(U\), \(D\), \(S\), theo đúng thứ tự này, cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả \(N\) hội chợ theo thứ tự tùy ý. Dòng thứ \(k\) trong số này mô tả hội chợ thứ \(k\), gồm ba số nguyên cách nhau bởi một dấu cách: ngày tổ chức \(T_k\), vị trí \(L_k\) và số tiền người bán hàng thu được khi tham dự \(M_k\).

Tất cả các vị trí trong dữ liệu vào đều khác nhau. Nghĩa là không có hai hội chợ nào diễn ra tại cùng một vị trí, và không có hội chợ nào diễn ra tại nhà của người bán hàng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: lợi nhuận lớn nhất mà người bán hàng có thể đạt được khi kết thúc hành trình.

Ràng buộc

• \(1 \le N \le 500\,000\): số hội chợ.
• \(1 \le D \le U \le 10\): chi phí đi một mét ngược dòng (\(U\)) hoặc xuôi dòng (\(D\)).
• \(1 \le S \le 500\,001\): vị trí nhà của người bán hàng.
• \(1 \le T_k \le 500\,000\) với \(1 \le k \le N\): ngày tổ chức hội chợ thứ \(k\).
• \(1 \le L_k \le 500\,001\) với \(1 \le k \le N\): vị trí hội chợ thứ \(k\).
• \(1 \le M_k \le 4\,000\) với \(1 \le k \le N\): số đô la thu được khi tham dự hội chợ thứ \(k\).

Phân nhóm

Một số bộ dữ liệu có tổng cộng \(60\) điểm thỏa mãn điều kiện không có hai hội chợ nào diễn ra cùng ngày.

Một số bộ dữ liệu có tổng cộng \(40\) điểm thỏa mãn điều kiện không có số nào trong dữ liệu vào vượt quá \(5\,000\).

Các bộ dữ liệu thỏa mãn cả hai điều kiện trên có tổng cộng \(15\) điểm.

Các bộ dữ liệu thỏa mãn ít nhất một trong hai điều kiện trên có tổng cộng \(85\) điểm.

Ví dụ

4 5 3 100
2 80 100
20 125 130
10 75 150
5 120 110

50

Nguồn

IOI 2009, ngày thi thứ hai: Salesman, bản tiếng Anh 1.2. Tác giả đề bài: Velin Tzanov. Tập đề bài và lời giải IOI 2009.