Wall Repair

Mirek repairs monuments for a living. Today he has to fix the defense wall of an old fortress. The wall is about to fall to pieces, so he must hurry. He tracked down a robot built to repair such walls very fast and bought it, then got stuck working out the cheapest repair plan.

Treat the wall as a straight line. Mirek wrote down the coordinate of every point that needs repairing. Repairing point $i$ right away costs $C_i$, and a coefficient $D_i$ says how fast that cost grows while the point waits. If point $i$ is repaired after time $t$ has passed, repairing it costs

$C_i + t \cdot D_i$

Moving the robot from coordinate $x_1$ to coordinate $x_2$ takes $|x_1 - x_2|$ time, and repairing one point takes no time. Time is measured from the moment the robot leaves its starting position. Find the minimum cost of repairing every damaged point.

The first line contains two integers $N$ and $P$, the number of points that need repairing and the starting position of the robot. ($1 \le N \le 2000$, $0 \le P \le 10^9$)

Each of the next $N$ lines describes one point with three integers $X_i$, $C_i$, $D_i$, which are the coordinate of the point and its two cost coefficients. ($0 \le X_i \le 10^9$, $0 \le C_i, D_i \le 10^6$, $X_i \ne P$)

No two points have the same coordinate.

Print on one line the integer $C$, the minimum cost of repairing all points on the wall. The value can exceed the range of a 32-bit integer.

The optimal plan for the first example is:

• Move the robot from coordinate 7 to coordinate 10 and repair the first point at time 3.
• Move the robot from coordinate 10 to coordinate 14 and repair the third point at time $3 + 4 = 7$.
• Move the robot from coordinate 14 to coordinate 3 and repair the second point at time $3 + 4 + 11 = 18$.

The total cost is $(32 + 3 \cdot 1) + (5 + 18 \cdot 1) + (0 + 7 \cdot 2) = 72$.