D - 会議室の予約 解説 /

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

配点 : 400 点

問題文

高橋君はある会社の会議室管理を担当しています。この会議室では、1 日を T 個の時間枠（時間枠 1, 2, \ldots, T）に分けて運用しており、各時間枠には同時に 1 件の会議しか割り当てることができません。

ある日、N 件の会議室利用の申請が届きました。

i 番目（1 \leq i \leq N）の申請は、時間枠 L_i から時間枠 R_i まで（両端を含む）の連続した時間枠に会議室を使用したいというものです。i 番目の申請を承認した場合、会社は V_i 円の利益を得ることができます。

高橋君は、これらの N 件の申請の中から 0 件以上を選んで承認します。ただし、同じ申請を複数回承認することはできず、承認した申請のうちどの 2 件をとっても、使用する時間枠が重なってはいけません。ここで、申請 i と申請 j（i \neq j）の時間枠が重なっているとは、閉区間 [L_i, R_i] と [L_j, R_j] に共通する整数が存在すること、すなわち L_i \leq R_j かつ L_j \leq R_i が成り立つことを指します。

承認する申請の選び方を最適にしたときの、承認した申請の利益の合計（すなわち、承認した申請の V_i の総和）の最大値を求めてください。1 件も承認しない場合の利益の合計は 0 円とします。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq T（1 \leq i \leq N）
  • 1 \leq V_i \leq 10^9（1 \leq i \leq N）
  • 入力はすべて整数である。

入力

N T
L_1 R_1 V_1
L_2 R_2 V_2
\vdots
L_N R_N V_N
  • 1 行目には、申請の件数 N と時間枠の総数 T がスペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、i 番目の申請の開始時間枠 L_i、終了時間枠 R_i、および利益 V_i がスペース区切りで与えられる。

出力

利益の合計の最大値を 1 行で出力せよ。

入力例 1

3 5
1 3 5
2 4 6
4 5 3

出力例 1

8

入力例 2

4 3
1 2 3
1 3 7
2 3 4
1 1 2

出力例 2

7

入力例 3

10 20
1 5 10
3 7 15
6 10 12
8 12 8
11 15 20
1 3 7
4 6 9
7 9 11
10 14 14
15 20 18

出力例 3

59

入力例 4

20 50
1 5 100
3 8 150
6 10 120
9 15 200
12 18 180
16 20 90
19 25 160
22 28 140
26 30 110
29 35 170
32 38 130
36 40 190
1 3 80
4 7 95
8 11 105
14 17 115
21 24 85
30 34 145
37 42 175
43 50 250

出力例 4

1230

入力例 5

1 1
1 1 1000000000

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi is in charge of managing a meeting room at a company. This meeting room operates by dividing each day into T time slots (time slots 1, 2, \ldots, T), and only 1 meeting can be assigned to each time slot at a time.

One day, N requests for meeting room usage were received.

The i-th request (1 \leq i \leq N) is to use the meeting room for consecutive time slots from time slot L_i to time slot R_i (inclusive). If the i-th request is approved, the company earns a profit of V_i yen.

Takahashi will select and approve 0 or more of these N requests. However, the same request cannot be approved more than once, and for any 2 approved requests, their time slots must not overlap. Here, the time slots of request i and request j (i \neq j) overlap means that there exists a common integer in the closed intervals [L_i, R_i] and [L_j, R_j], that is, L_i \leq R_j and L_j \leq R_i both hold.

Find the maximum total profit of the approved requests (i.e., the maximum sum of V_i over all approved requests) when the selection of requests to approve is optimized. If no requests are approved, the total profit is 0 yen.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq T (1 \leq i \leq N)
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N T
L_1 R_1 V_1
L_2 R_2 V_2
\vdots
L_N R_N V_N
  • The first line contains the number of requests N and the total number of time slots T, separated by a space.
  • The following N lines, where the i-th line (1 \leq i \leq N), contains the starting time slot L_i, ending time slot R_i, and profit V_i of the i-th request, separated by spaces.

Output

Output the maximum total profit in a single line.

Sample Input 1

3 5
1 3 5
2 4 6
4 5 3

Sample Output 1

8

Sample Input 2

4 3
1 2 3
1 3 7
2 3 4
1 1 2

Sample Output 2

7

Sample Input 3

10 20
1 5 10
3 7 15
6 10 12
8 12 8
11 15 20
1 3 7
4 6 9
7 9 11
10 14 14
15 20 18

Sample Output 3

59

Sample Input 4

20 50
1 5 100
3 8 150
6 10 120
9 15 200
12 18 180
16 20 90
19 25 160
22 28 140
26 30 110
29 35 170
32 38 130
36 40 190
1 3 80
4 7 95
8 11 105
14 17 115
21 24 85
30 34 145
37 42 175
43 50 250

Sample Output 4

1230

Sample Input 5

1 1
1 1 1000000000

Sample Output 5

1000000000