配点 : 100 点
問題文
海龟君和大结君现在 D 天 我计划从事 N 工作。工作有序 编号 1, 2 \ldots N 已分配并且工作 i 内容如下:
- T_i = 1 当龟君 L_i 从第一天开始 R_i 当天工作。奖励是 1 已获得。
- T_i = 2 当大结君 在 L_i 从第一天开始 R_i 当天工作。奖励是 1 已获得。
- T_i = 3 时,海龟君和大结君共同 L_i 从第一天开始 R_i 当天工作。奖励是 V_i 已获得。
乌龟君和大结君是 选择一些N 任务并完成它们。在这种情况下,无论工作类型如何,同一个人都会在同一日期工作。 2 您不得从事超过一份工作。求海龟君和大结君能得到的奖励之和的最大值。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq D \leq 10^9
- T_i 是 您也可以写 1,2,3 (1 \leq i \leq N)
- 1 \leq L_i \leq R_i \leq D (1 \leq i \leq N)
- T_i = 3 时,1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N D
\mathrm{work}_1
\mathrm{work}_2
\vdots
\mathrm{work}_N
各 \mathrm{work}_i 包含多个以空格分隔的整数。 1 眼睛 T_i 。 \mathrm{work}_i 采用以下格式之一:
1 L_i R_i
2 L_i R_i
3 L_i R_i V_i
出力
打印答案。 来自
入力例 1
5 5 1 1 2 1 3 4 2 2 3 2 4 5 3 2 2 3
出力例 1
5
海龟君和大结君是 通过选择第 2,4,5 个职业,满足条件即可获得奖励。 5 可以实现。 具体来说, 完成第 2,4,5 个任务后,乌龟将 2,3,4 那天,大结君 2,4,5 当天工作 1 将一一收录。