分数: 400 分
问题陈述
高桥是一个活动场地的经理。
他收到了预订请求 N 事件。的 i第一个事件 (1 \leq i \leq N) 在时间段内使用场地 L_i 到时间 R_i.
两个事件 i, j 有 重叠 时间段(如果存在时间) t 这样 L_i \leq t < R_i 和 L_j \leq t < R_j。换句话说,当每个事件的时间段表示为半开区间时 [L_i, R_i),两个区间有非空交集。因此,如果一个事件的结束时间与另一个事件的开始时间一致(即,时间间隔仅在端点处接触),则它们不被视为重叠。
由于场地只有一个,因此无法同时接受时间段重叠的活动。高桥将接受一些 N 事件并拒绝其余事件。接受的事件集中的任何两个事件必须具有不重叠的时间段。还允许不接受任何事件(拒绝所有事件),或者如果没有重叠,则接受所有事件。
对于每个接受的事件,收入为 B 无论活动内容如何,均可赚取一万日元。另一方面,拒绝 i第一个活动产生的取消补偿费用为 C_i 一万日元。
高桥想要最大化 利润,这是已接受事件的总收入减去已拒绝事件的总取消补偿成本。
正式地,让 S \subseteq \{1, 2, \ldots, N\} 是一组接受的事件,条件是其中的任何两个事件 S 具有不重叠的时间段。最大化以下值:
\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
- 第一行包含一个整数 N 表示事件数量和一个整数 B 代表每个已接受事件的收入(单位为万日元),以空格分隔。
- 从第 2 行到 (N + 1)第行,给出每个事件的信息,每行一个事件。
- 的 树的 (1 + i)- 第行包含开始时间 L_i,结束时间 R_i,以及取消补偿费用 C_i (单位:万日元) i-第一个事件,以空格分隔的整数形式给出。
输出
在单行上以整数形式输出最大利润。
示例输入 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