Problem Description

Kazuma is attending the sports day at Kyukanba Elementary School. There are $ N $ events scheduled, each with an integer ID from $ 0 $ to $ N - 1 $.

The $ i $-th event starts at time $ A_i $ and ends at time $ B_i $. Participating in this event gives Kazuma $ F_i $ units of fun.

Due to the large size of the schoolyard, multiple events can be held simultaneously, meaning that the time slots of $ N $ events may overlap.

Kazuma cannot participate in events that overlap in time. However, he can participate in events that start immediately after another event ends. In other words, it is possible to participate in events where the end time matches the start time.

Kazuma wants to enjoy the sports day as much as possible. However, under the scorching summer sun, the longer he participates, the more his stamina depletes, reducing his fun. Specifically, participating for one unit of time reduces his fun by $ C $. This depletion continues even when not participating in events.

As Kazuma is an indoor person, he wants to efficiently participate in the sports day to avoid the heat. He can start participating at any time and leave at any time.

Find the maximum amount of fun Kazuma can obtain.

Input Format

$ N $ $ C $ $ A_1 $ $ B_1 $ $ F_1 $ : $ A_N $ $ B_N $ $ F_N $

Output Format

Output the solution in one line.

Sample Input and Output

Sample Input #1

5 3
1 4 12
3 6 7
2 3 6
4 8 8
8 9 10

Sample Output #1

7

Sample Input #2

5 2
1 4 12
3 6 7
2 3 6
4 8 8
8 9 10

Sample Output #2

14

Notes/Hints

Task

Given $ N $ intervals defined by integer arrays $ A $ and $ B $, the $ i $-th interval is a half-open interval $ [A_i, B_i) $ (including $ A_i $ but excluding $ B_i $). Each interval has a non-negative integer weight, where the weight of the $ i $-th interval is $ F_i $.

Consider selecting zero or more non-overlapping intervals from the given intervals. Let the set of selected interval indices be $ G $.

Define $L = \min \{A_i \mid i \in G \}$ and $R = \max \{B_i \mid i \in G \}$. The score of $ G $ is defined as $(\sum_{i \in G} F_i) - C \times (R - L)$, where $ C $ is a non-negative integer constant. The score of an empty set $ G $ is $ 0 $.

Maximize the score by choosing the elements of $ G $ appropriately.

Constraints

All input data satisfies the following constraints:

• $1 \leq N \leq 10^5$.
• $0 \leq C \leq 10^4$.
• $0 \leq A_i < B_i \leq 10^5$.
• $0 \leq F_i \leq 10^4$.

Additionally, partial points are awarded for inputs that satisfy the following additional constraint:

• $N \leq 1000$.

Sample Explanation 1

Choosing the 5th interval results in a score of $ 7 $, which is the maximum score achievable.

见题面 Input 部分

见题面 Output 部分