Attack the Moles

Time limit10sMemory limit512 MB

Summary

Two hands with speed limit V must hit moles at their exact times and positions, with the left hand always left of the right. Find the maximum total points.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting
Solved: No attempts yet

Problem

ICPC requires hard training to get good results. Usagi wants to win at ICPC, so today too, Usagi decides to train.

Today's training is whack-a-mole, played many times to sharpen reflexes and memory. Usagi wants to hit the moles as they appear and earn as many points as possible.

The possible mole locations lie on a straight line, and each location's coordinate is its distance from a reference point. While training, Usagi noticed that the location and time of each mole are always the same. Usagi recorded all of this information and decided to analyze it with a computer.

To hit a mole, Usagi must move a hand to the mole's location and strike at exactly the moment the mole appears. A successful hit earns the points for that mole. A strike takes an instant, but a hand can move only so fast. Usagi may use both the left and right hands. The two hands move independently, but the left hand must always stay at a smaller coordinate than the right hand. Find the maximum number of points Usagi can earn under these conditions.

Input

The first line contains $N$ , $V$ , $X_{Left}$ , and $X_{Right}$ , separated by spaces. They are the number of moles, the maximum speed at which a hand can move, and the initial coordinates of the left and right hands. Each of the next $N$ lines contains $X_i$ , $T_i$ , and $P_i$ : the coordinate where the $i$ -th mole appears, the time from the start of the game until it appears, and the points earned for hitting it.

N V XLeft XRight
X1 T1 P1
 ...
XN TN PN

The constraints are $1 \le N \le 3,000$ , $1 \le V \le 10,000$ , $1 \le X_{Left} < X_{Right} \le 100,000$ , $1 \le X_1 \le X_2 \le \cdots \le X_N \le 100,000$ , $1 \le T_i \le 100,000$ , and $1 \le P_i \le 100,000$ . No two moles share the same pair $(X_i, T_i)$ .

Output

Print the maximum number of points Usagi can earn on one line.

Examples3

Example 1

Input

3 10 150 250
100 20 123
201 10 67
202 10 45

Expected output

Example 2
Input
```
1 7 20 90
55 5 73
```
Expected output
```
73
```

Example 3

Input

10 2 1000 2000
400 300 1
600 200 1
700 800 1
700 500 1
900 600 1
1000 700 1
1300 900 1
1400 400 1
1500 1000 1
2000 100 1

Expected output