Problem Description

On a certain planet, a preliminary round of a programming contest called "The Challenge from Dwango" was held, and the qualifiers were invited to the main event venue.

This planet has a single circular railway line of length $ L $, and there are $ N $ cities on this circular line. The cities are numbered from $ 1 $ to $ N $ in ascending order clockwise starting from city $ 1 $.

The main event will be held in one or more cities, and live broadcasts will be conducted at each venue.

The number of qualifiers living in each city and the number of qualifiers entering each venue are predetermined.

The total number of qualifiers entering the venues exactly matches the total number of qualifiers.

In some cities, the number of qualifiers living there does not match the number of qualifiers entering the venue, in which case qualifiers need to be moved between cities by taxi.

Taxis move along the circular railway line, and the cost of moving each qualifier is equal to the distance traveled.

Write a program to find the minimum possible total cost of the moves.

Input Format

The input is given from the standard input in the following format:

$ N $ $ L $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ : $ a_N $ $ b_N $ $ c_N $

• The first line contains the number of cities $N\ (2\ ≦\ N\ ≦\ 100,000)$ and the length of the circular line $L\ (N\ ≦\ L\ ≦\ 10,000,000)$, separated by spaces.
• The next $ N $ lines contain information about each city. The $i\ (1\ ≦\ i\ ≦\ N)$ line contains three integers $a_i\ (0\ ≦\ a_i\ ≦\ L\ -\ 1)$, $b_i\ (0\ ≦\ b_i\ ≦\ 100,000)$, and $c_i\ (0\ ≦\ c_i\ ≦\ 100,000)$, separated by spaces. This indicates that city $ i $ is located $ a_i $ units clockwise from city $ 1 $ on the circular line, the number of qualifiers leaving city $ i $ is $ b_i $, and if $c_i\ =\ 0$, there is no venue in city $ i $, otherwise, city $ i $ has a venue that can accommodate $ c_i $ qualifiers.
• $a_1\ =\ 0$, and for all integers $i\ (2\ ≦\ i\ ≦\ N)$, $a_i\ ＞\ a_{i-1}$ holds.
• $b_1\ +\ ...\ +\ b_N\ =\ c_1\ +\ ...\ +\ c_N$.
• $b_1\ +\ ...\ +\ b_N\ ≧\ 1$.

Output Format

Output the minimum possible total move cost in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

7 30
0 3 6
1 2 2
4 5 4
19 0 1
20 4 4
21 1 0
27 3 1

Sample Output #1

12

Sample Input #2

6 25
0 10 1
3 0 1
9 0 2
12 0 3
13 0 2
21 0 1

Sample Output #2

85

Notes/Hints

Partial Points

This problem has partial points.

• For a dataset where $N\ ≦\ 5,000$ and $b_1\ +\ ...\ +\ b_N\ ≦\ 5,000$, correct answers will earn $ 15 $ points.
• For a dataset where $N\ ≦\ 5,000$, correct answers will earn an additional $ 30 $ points.
• For a dataset with no additional constraints, correct answers will earn an additional $ 55 $ points, totaling $ 100 $ points.

Sample Explanation 1

Consider the following moves:
- One qualifier from city $ 3 $ moves counterclockwise to city $ 1 $ by taxi. The move cost is $4\ ×\ 1\ =\ 4$.
- One qualifier from city $ 6 $ moves counterclockwise to city $ 4 $ by taxi. The move cost is $2\ ×\ 1\ =\ 2$.
- Two qualifiers from city $ 7 $ move clockwise to city $ 1 $ by taxi. The total move cost is $3\ ×\ 2\ =\ 6$.

As a result of these moves, in every city with a venue, the number of qualifiers entering the venue equals the number of qualifiers in the city, and all qualifiers can enter a venue. The total move cost is $4\ +\ 2\ +\ 6\ =\ 12$, which is the minimum value.

见题面 Input 部分

见题面 Output 部分