Task DescriptionDiscussion (0)

1 ≤

1 ≤

1 ≤

1 ≤

1 ≤

1 ≤

Your program must read from standard input the following data:

• The first line contains the integers

• The next N lines describe the N fairs in no particular order. The

of these N lines describes the

NOTE: All locations given in the input will be different. That is to say, no two fairs will happen at the same location and no fair will happen at the salesman’s home.

Your program must write to standard output a single line containing a single integer: the maximum profit the salesman can possibly make by the end of his journey.

An optimal schedule would visit fairs 1 and 3 (the ones at locations 80 and 75). The sequence of events and their associated prots and costs would be as follows:

• The salesman travels 20 meters upstream at a cost of 100 dollars. Profit so

far: -100

• He attends fair number 1 and earns 100. Profit so far: 0

• He travels 5 meters upstream at a cost of 25. Profit so far: -25

• He attends fair number 3 where he earns 150. Profit so far: 125

• He travels 25 meters downstream to return home at a cost of 75. Profit at the end: 50

Task :: Salesman

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 the salesman

**U**dollars for every meter traveled upstream (towards the source of the river) and**D**dollars for every meter traveled downstream (away from the source of the river).There are

**N**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 X, the traveling salesman knows its date**T**, measured in the number of days since he purchased his boat. He also knows the fair’s location_{X}**L**, measured as the distance in meters from the source of the river downstream to the fair, as well as the number of dollars_{X}**M**that the salesman is going to gain if he attends this trade fair. He has to start and end his journey at his waterfront home on the river, which is at location S, measured also in meters downstream from the source of the river._{X}Help the traveling salesman choose which trade fairs to attend (if any) and in what order, so that he may maximize his profit at the end of his travels. The traveling salesman’s total profit is defined as the sum of the dollars he gained at the fairs he attended, minus the total sum of dollars he spent traveling up and down the river.

Keep in mind that if trade fair

**A**is held earlier than trade fair B, the salesman can visit them only in this order (i.e., he cannot visit**B**and then visit**A**). However, if two fairs are held on the same date, the salesman can visit them both in any order. There is no limit to how many fairs the salesman can visit in a day, but naturally he can't visit the same fair twice and reap the gains twice. He can pass through fairs he has already visited without gaining anything.Write a program that, given the date, location and profitability of all fairs, as well as the location of the traveling salesman’s home and his costs of traveling,determines the maximum possible profit he can make by the end of his journey.

**INPUT:**

1 ≤

**N**≤ 500,000 The number of fairs

1 ≤

**D**≤

**U**≤ 10 The cost of traveling one meter upstream (U) or downstream (D)

1 ≤

**S**≤ 500,001 The location of the salesman’s home

1 ≤

**T**≤ 500,000 The day on which fair k is held

_{k}1 ≤

**L**≤ 500,001 The location of fair k

_{k}1 ≤

**M**≤ 4,000 The number of dollars the salesman would earn if he attends fair

_{k}**k**

Your program must read from standard input the following data:

• The first line contains the integers

**N**,

**U**,

**D**and

**S**, in this order, separated by single spaces.

• The next N lines describe the N fairs in no particular order. The

**k**'th

of these N lines describes the

**k**'th fair and contains three integers separated by single spaces: the day of the fair

**T**, its location

_{k}**L**, and its profitability for the salesman

_{k}**M**.

_{k}NOTE: All locations given in the input will be different. That is to say, no two fairs will happen at the same location and no fair will happen at the salesman’s home.

**OUTPUT:**

Your program must write to standard output a single line containing a single integer: the maximum profit the salesman can possibly make by the end of his journey.

Input

Output

**4 5 3 100**

2 80 100

20 125 130

10 75 150

5 120 110

2 80 100

20 125 130

10 75 150

5 120 110

Output

**50**

**Explanation**

An optimal schedule would visit fairs 1 and 3 (the ones at locations 80 and 75). The sequence of events and their associated prots and costs would be as follows:

• The salesman travels 20 meters upstream at a cost of 100 dollars. Profit so

far: -100

• He attends fair number 1 and earns 100. Profit so far: 0

• He travels 5 meters upstream at a cost of 25. Profit so far: -25

• He attends fair number 3 where he earns 150. Profit so far: 125

• He travels 25 meters downstream to return home at a cost of 75. Profit at the end: 50

Submit Solution

Available Languages

Task info

Task Ratings

Difficulty: | 4.8 (6 votes) |

Quality: | 4.8 (5 votes) |

Acceptance Rate

Recent Submissions

Fastest Solutions

User | Time |
---|---|

fetofs | 1.863 s. |

mateuscd11 | 2.164 s. |

harta01 | 2.5 s. |

1010011010 | 2.902 s. |

Alan_C | 3.38 s. |

whatsgoingon | 3.412 s. |

stjepang | 3.492 s. |

Kusika | 3.934 s. |

Amtrix | 4.099 s. |

illusion | 4.17 s. |

Solved By