Traveling Salesman on the Danube

The traveling salesman has shifted his business from difficult overland trips to the linear world along the Danube. He owns a fast boat that can take him from any point along the river to any other in a very short time; however, the boat consumes a lot of fuel. When he travels 1 meter upstream (toward the river’s source) the cost is U dollars per meter, and when he travels 1 meter downstream (away from the source) the cost is D dollars per meter.

There are N fairs located along the river, each held on a single day. For each fair X, the salesman knows its day T_X (with day 0 being the day he bought the boat), its location L_X (the distance in meters from the river’s source), and the profit M_X dollars he would earn by attending it. He must start and end his journey at his home located at position S.

He can only attend fairs in non‐decreasing order of their dates, i.e. if fair A is held before fair B then A must be visited before B. (If two fairs are held on the same day, he can visit them in any order.) There is no limit on how many fairs he can attend in one day, but he cannot earn profit from the same fair twice. He may pass by a fair he has already visited without gaining extra profit.

The total profit is defined as the sum of the earnings from the fairs he attends minus the total cost of his boat travels along the river. The cost to travel from point a to point b is computed as follows:

• If b >= a (traveling downstream) the cost is
  \( (b - a)\times D \).
• If b < a (traveling upstream) the cost is
  \( (a - b)\times U \).

Your task is to choose which fairs to attend (if any) and in which order (subject to the above constraints) so that the salesman’s profit at the end of his trip is maximized.

Note: The journey must start and end at his home at position S.

inputFormat

The first line contains four integers: N (the number of fairs), S (the home location on the river), U (the cost per meter when traveling upstream), and D (the cost per meter when traveling downstream).

Each of the following N lines contains three integers: T_X (the day the fair is held), L_X (the location of the fair), and M_X (the profit from attending the fair).

Constraints: It is guaranteed that M_X is non‐negative. Fairs held on the same day can be visited in any order.

outputFormat

Output a single integer, representing the maximum profit the salesman can achieve (total earnings from fairs minus the total traveling cost) if he plans his journey optimally.

sample

3 10 2 1
1 5 10
2 15 20
2 10 5

5