Merchant

A merchant found planning an optimal trip over land far too hard, so he decided to travel along a straight river, selling goods as he goes. He owns a very fast boat that can move instantly from any point on the river to any other point, but the boat burns a lot of fuel. Moving upstream (toward where the river begins) costs $U$ dollars per meter, and moving downstream (with the current) costs $D$ dollars per meter.

There are $N$ markets the merchant wants to visit, and each market is open for exactly one day. For each market $k$ you are given, counted from the day he bought the boat, the day $T_k$ on which it is open, its distance $L_k$ (in meters) from the source of the river, and the profit $M_k$ (in dollars) he gains by visiting it. The merchant's home is at distance $S$ from the source of the river. He starts at home, visits any markets he chooses, and returns home to finish the trip.

You must decide which markets to visit and in what order so that his total profit is maximized. (He may visit no market at all.) His total profit equals the sum of the profits of the markets he visits minus the fuel cost of moving up and down the river.

If he visits two markets, he must visit them in the order of the days on which they open. For example, if market $A$ opens before market $B$, he cannot visit market $B$ first and then market $A$. However, if two markets open on the same day, he may visit them in either order. There is no limit on how many markets he can visit in one day. He cannot visit the same market twice to double its profit, but he may pass through an already-visited market without gaining its profit again.

Given the boat's per-meter fuel costs, the merchant's home position, and each market's day, position, and profit, write a program that computes the maximum profit he can obtain after finishing the trip.

The first line contains the integers $N$, $U$, $D$, and $S$, separated by single spaces.

Each of the next $N$ lines describes one market, in no particular order. The $k$-th of these lines contains three integers $T_k$, $L_k$, and $M_k$, separated by single spaces: the day the market is open, the market's position, and the profit gained by visiting it.

All market positions are distinct, and no market is located at the merchant's home. That is, no two markets share a position and $L_k \ne S$.

• $1 \le N \le 500{,}000$ (number of markets)
• $1 \le D \le U \le 10$ (cost per meter is $U$ going upstream and $D$ going downstream)
• $1 \le S \le 500{,}001$ (position of the merchant's home)
• $1 \le T_k \le 500{,}000$ (day market $k$ is open)
• $1 \le L_k \le 500{,}001$ (position of market $k$)
• $1 \le M_k \le 4{,}000$ (profit from visiting market $k$)

Print a single integer on one line: the maximum profit the merchant can obtain after finishing the trip.

Consider the example. The home is at position $100$, and the optimal schedule is to visit the market at position $80$ (open on day $2$) and the market at position $75$ (open on day $10$). The order of visits and the running profit are as follows.

• Move $20$ meters upstream to position $80$, costing $5 \times 20 = 100$ dollars. (running profit $-100$)
• Visit the market at position $80$ and gain $100$ dollars. (running profit $0$)
• Move $5$ more meters upstream to position $75$, costing $5 \times 5 = 25$ dollars. (running profit $-25$)
• Visit the market at position $75$ and gain $150$ dollars. (running profit $125$)
• Move $25$ meters downstream back home to position $100$, costing $3 \times 25 = 75$ dollars. (final profit $50$)

Therefore the maximum profit is $50$ dollars.