Background

JYY really likes going to the arcade to play Whac-a-Mole—picking up two hammers and hitting the moles that keep popping out.

Hitting different moles gives different scores, and JYY wants to know how to get the highest score.

Problem Description

In the game, a total of $N$ moles will appear, and their positions are all on a straight line. The $i$-th mole appears at position $X_i$ at time $T_i$, and the score for hitting the $i$-th mole is $P_i$.

When the game starts (that is, at time $0$), JYY’s left hand is at position XLEFT, and the right hand is at position XRIGHT. The maximum moving speed of JYY’s hands is $V$ (the maximum distance moved per unit time is $V$).

Each mole appears and disappears instantly. If at the corresponding time, one of JYY’s hands is exactly at the position where the mole appears, then JYY can complete the hit instantly and get the corresponding score. Otherwise, JYY can only miss this mole.

Since JYY holds hammers in both hands, the two hands can hit moles at the same time.

However, if JYY’s two hands cross during the game, JYY will feel very uncomfortable (the movement is indeed awkward, and the two hands may block each other and affect the moving speed). Therefore, JYY hopes that throughout the whole game, the left hand position XLEFT is always strictly less than the right hand position XRIGHT. JYY wants to know the maximum total score he can get.

Input Format

The first line contains four integers $N,~V,~XLEFT,~XRIGHT$. The next $N$ lines describe the $N$ possible moles. The $i$-th line contains three integers $X_i$, $T_i$, $P_i$. The testdata guarantees that at the same time, there will not be two moles appearing at the same position.

Output Format

Output one line with one integer, meaning the maximum score JYY can get.

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

190

Hint

Constraints.

$1~\leq~N~\leq~3000,~1~\leq~XLEFT~<~XRIGHT~\leq~10^5,~1~\leq~T_i~\leq~10^5$

$1~\leq~P_i~\leq~10^5,~1~\leq~X_i~\leq~10^5,~1~\leq~V~\leq~10^4$

Translated by ChatGPT 5