D - イベント会場の予約 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君はイベント会場の管理者です。

N 件のイベントの予約申請が届いており、i 番目のイベント (1 \leq i \leq N) は時刻 L_i から時刻 R_i までの時間帯に会場を使用します。

2 つのイベント i, j の使用時間帯が重なるとは、ある時刻 t が存在して L_i \leq t < R_i かつ L_j \leq t < R_j を満たすことをいいます。言い換えると、各イベントの使用時間帯を半開区間 [L_i, R_i) で表したとき、2 つの区間が共通部分を持つことを意味します。したがって、一方のイベントの終了時刻と他方の開始時刻が一致する場合（端点で接する場合）は重なりとはみなしません。

会場は 1 つしかないため、使用時間帯が重なるイベントを同時に受理することはできません。高橋君は N 件のイベントのうち一部を受理し、残りを却下します。受理するイベントの集合に含まれるどの 2 つのイベントも使用時間帯が重ならないようにしなければなりません。なお、1 つも受理しない（すべて却下する）ことや、重なりがなければすべて受理することも許されます。

イベントを 1 件受理するごとに、イベントの内容によらず一律 B 万円の収益が得られます。一方、i 番目のイベントを却下すると、キャンセル補償として C_i 万円の費用がかかります。

高橋君は、受理したイベントから得られる収益の合計から、却下したイベントのキャンセル補償費用の合計を引いた利得を最大化したいです。

すなわち、受理するイベントの集合を S \subseteq \{1, 2, \ldots, N\} とし、S に含まれるどの 2 つのイベントも使用時間帯が重ならないという条件のもとで、次の値を最大化してください。

\displaystyle |S| \times B - \sum_{i \in \{1,\ldots,N\} \setminus S} C_i

この最大値を求めてください。なお、答えが負になる場合もあります。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq B \leq 10^9
  • 0 \leq L_i < R_i \leq 10^9
  • 1 \leq C_i \leq 10^9
  • 入力はすべて整数である。

入力

N B
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_N R_N C_N
  • 1 行目には、イベントの件数を表す整数 N と、受理 1 件あたりの収益（万円）を表す整数 B が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各イベントの情報が 1 行ずつ与えられる。
  • 1 + i 行目には、i 番目のイベントの使用開始時刻 L_i、使用終了時刻 R_i、却下時のキャンセル補償費用 C_i（万円）が、スペース区切りの整数で与えられる。

出力

利得の最大値を整数として 1 行で出力せよ。

入力例 1

3 10
0 3 5
2 5 3
5 8 4

出力例 1

17

入力例 2

2 1
0 5 100
1 6 100

出力例 2

-99

入力例 3

8 15
0 10 5
5 20 8
10 25 3
20 30 12
25 35 7
30 40 6
35 50 9
0 50 100

出力例 3

-35

入力例 4

15 100
0 10 50
5 15 30
10 20 40
15 25 60
20 30 20
25 35 70
30 40 10
35 45 55
40 50 25
45 55 80
50 60 15
55 65 35
60 70 45
65 75 90
70 80 65

出力例 4

450

入力例 5

1 1000000000
0 1000000000 1000000000

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi is the manager of an event venue.

He has received reservation requests for N events. The i-th event (1 \leq i \leq N) uses the venue during the time period from time L_i to time R_i.

Two events i, j have overlapping time periods if there exists a time t such that L_i \leq t < R_i and L_j \leq t < R_j. In other words, when each event's time period is represented as a half-open interval [L_i, R_i), the two intervals have a non-empty intersection. Therefore, if one event's end time coincides with another's start time (i.e., the intervals only touch at an endpoint), they are not considered overlapping.

Since there is only one venue, events with overlapping time periods cannot be accepted simultaneously. Takahashi will accept some of the N events and reject the rest. Any two events in the set of accepted events must have non-overlapping time periods. It is also allowed to accept no events (reject all) or, if there are no overlaps, to accept all events.

For each accepted event, a revenue of B ten-thousand yen is earned, regardless of the event's content. On the other hand, rejecting the i-th event incurs a cancellation compensation cost of C_i ten-thousand yen.

Takahashi wants to maximize the profit, which is the total revenue from accepted events minus the total cancellation compensation costs for rejected events.

Formally, let S \subseteq \{1, 2, \ldots, N\} be the set of accepted events, subject to the condition that any two events in S have non-overlapping time periods. Maximize the following value:

\displaystyle |S| \times B - \sum_{i \in \{1,\ldots,N\} \setminus S} C_i

Find this maximum value. Note that the answer may be negative.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq B \leq 10^9
  • 0 \leq L_i < R_i \leq 10^9
  • 1 \leq C_i \leq 10^9
  • All input values are integers.

Input

N B
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_N R_N C_N
  • The first line contains an integer N representing the number of events and an integer B representing the revenue per accepted event (in ten-thousand yen), separated by a space.
  • From the 2nd line to the (N + 1)-th line, the information for each event is given, one event per line.
  • The (1 + i)-th line contains the start time L_i, end time R_i, and cancellation compensation cost C_i (in ten-thousand yen) for the i-th event, given as space-separated integers.

Output

Output the maximum profit as an integer on a single line.

Sample Input 1

3 10
0 3 5
2 5 3
5 8 4

Sample Output 1

17

Sample Input 2

2 1
0 5 100
1 6 100

Sample Output 2

-99

Sample Input 3

8 15
0 10 5
5 20 8
10 25 3
20 30 12
25 35 7
30 40 6
35 50 9
0 50 100

Sample Output 3

-35

Sample Input 4

15 100
0 10 50
5 15 30
10 20 40
15 25 60
20 30 20
25 35 70
30 40 10
35 45 55
40 50 25
45 55 80
50 60 15
55 65 35
60 70 45
65 75 90
70 80 65

Sample Output 4

450

Sample Input 5

1 1000000000
0 1000000000 1000000000

Sample Output 5

1000000000