Salesman#294
The traveling salesman has decided that optimally scheduling his trips on land is an intractable computational problem, so he is moving his business to the linear world of the Danube River. He has a very fast boat that can get him from anywhere to anywhere along the river in no time, but unfortunately the boat has terrible fuel consumption: it costs him dollars for every meter traveled upstream (towards the source of the river), and dollars for every meter traveled downstream (away from the source).
There are trade fairs that the salesman would like to visit along the river. Each trade fair is held for one day only. For each trade fair , the salesman knows its date T_x, measured in number of days since he purchased his boat. He also knows the fair's location L_x, measured as the distance in meters from the source of the river downstream to the fair, as well as the number of dollars M_x that he would gain if he attends that trade fair. He has to start and finish his journey at his waterfront home on the river, which is at location , also measured in meters downstream from the source.
Help the traveling salesman choose which trade fairs to attend (if any), and in what order, so that he maximizes his profit at the end of his travels. The total profit is defined as the sum of the dollars gained at the fairs attended, minus the total sum of dollars spent traveling up and down the river.
Note:
If trade fair is held earlier than trade fair , then the salesman can only visit before (he cannot visit and then ).
If two fairs are held on the same date, the salesman can visit them both in any order on that date.
There is no limit to how many fairs may be visited in a day, but he cannot visit the same fair more than once. He can pass through fairs already visited without gaining anything.
Write a program that, given the dates, locations and profitability of all fairs, as well as the home location and travel costs, determines the maximum possible profit he can make by the end of his journey.
The first line contains four integers , , , and : the number of fairs, the cost per meter upstream, the cost per meter downstream, and the location of the salesman's home (1 \le N \le 500\ 000, 1 \le D \le U \le 10, 1 \le S \le 500\ 001).
The next lines each contain three integers T_k, L_k, M_k: the day of the -th fair, the location of the -th fair, and the dollars gained by visiting the -th fair (1 \le T_k \le 500\ 000, 1 \le L_k \le 500\ 001, 1 \le M_k \le 4\ 000).
All L_k are distinct; no fair is held at the salesman's home.
Output a single integer: the maximum possible profit the salesman can achieve by the end of his journey.
Example 1