← 返回题目列表

AtCoder · pakencamp_2024_day3_1_e

E. 团队合作

中文机器翻译题面 查看原题

配点 : 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 将一一收录。