12822번 - Wall 다국어

Mirek is a conservator. His job is to maintain monuments, keeping them in good condition. Mirek’s today task is to repair the defense wall of an old fortress. The wall is about to fall to pieces, so he must hurry. He searched through the Internet and found a robot designed to repair such walls extremely fast. After purchasing the robot, he tried to make the optimal repairment plan, but this was way too difficult for him.

The wall can be considered as a straight line. Mirek wrote down all points on the wall, which require repairing. For each point he knows, what would be the cost C_i of repairing it, and a coefficient D_i – how would the cost increase if it wasn’t repaired immediately. If the i-th point will be repaired after time t, then the cost of repairing it would be equal to:

Ci + t · Di

Given the coordinates of all points on the wall and the initial position of the robot, and knowing that transportation of the robot from point x₁ to point x₂ would take |x₁ − x₂| time, calculate the minimum cost of repairing all spoiled points. You can assume that repairing a single point takes no time.

On the first line of input there are two integers N and P (1 ≤ N ≤ 2 000, 0 ≤ P ≤ 10⁹) – the number of points on the wall, which should be repaired, and the initial position of the robot. Then, N lines follow, i-th of these lines describes i-th point on the wall and contains three integers X_i , C_i and D_i (0 ≤ X_i ≤ 10⁹ , 0 ≤ C_i , D_i ≤ 10⁶ , X_i ≠ P) – the position of the point and cost coefficients. There are no two points with equal positions.

Output a single line with integer C, where C is the minimal cost of repairing all points on the wall.

The optimal plan of repairing points is:

• Transport robot from point 7 to point 10 and repair the first point after time 3.
• Transport robot from point 10 to point 14 and repair the third point after time 3 + 4 = 7.
• Transport robot from point 14 to point 3 and repair the second point after time 3+4+11 = 18.

Thus, the total cost of repairing the wall is 5 + 18 · 1 + 32 + 3 · 1 + 0 + 7 · 2 = 72.