← 返回题目列表

AtCoder · awc0090_d

D. 活动场地预订

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

分数: 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