← 返回题目列表

AtCoder · k4pc_d

D. 学校运动很有趣

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

問題文

和真君要来参加休观场小学的运动会。 N 比赛举行,每场比赛包括 它的整数为 0 减去 N - 1 。

i 第一场比赛时间到了 时间从 A_i 开始 在 B_i 结束时,和真君参加了这次比赛。 您可以享受 F_i 。

休堪哈小学的操场很大,所以可以同时举行多项运动。换句话说, N 多种类型比赛的比赛时间可能会重叠。

Kazuma 不能参加具有相同开始时间的比赛。但是,他可以参加一场比赛结束后立即开始的另一场比赛。换句话说,可以参加具有相同结束时间和开始时间的比赛。

和真想尽可能地享受运动会,但在盛夏的烈日下参加运动会的时间越长,他的体力消耗就越多,他的乐趣也就越多。具体来说, 1 当您参加单位时间运动会时 C 和真的乐趣将会减少。而且,即使此时他不参加比赛,他的体力也会不断下降。

由于 Kazuma 是一个室内人,他希望高效地参加运动会并避开炎热的天气。换句话说,和真可以随时开始参加运动会,也可以随时回家。

在这种情况下,求 Kazuma 可以获得的最大乐趣。

課題

N 间隔是整数序列 它由 A, B 给出。i 第一个区间是半开区间 包括 [A_i, B_i) (A_i ,但是 B_i 不包括在内)。此外,每个区间都有一个非负整数的权重, 第i 个区间的权重为 F_i 是。

给定区间中,相互不重叠的区间 考虑到选择多于 0 个间隔,所选间隔的数字集合为 比方说 G 。

此时, 当 L = min \{A_i | i \in G \}, R = max\{B_i | i \in G\} 时,非负整数常量 使用 C 的值 我们将其称为 (Σ _{i \in G} F_i) - C \times (R - L) 该值应乘以 G 的分数。然而, 当 G 为空集时,得分为 0 。 如果

嗯 选择 G 的元素时得分最大化。


制約

所有输入数据满足以下否定条件。

  • 1 ≦ N ≦ 10^5.
  • 0 ≦ C ≦ 10^4.
  • 0 ≦ A_i < B_i ≦ 10^5.
  • 0 ≦ F_i ≦ 10^4.

另外,本题设有部分分数,1 分的输入数据额外满足以下否定条件。

  • N ≦ 1000.

入力

N C
A_1 B_1 F_1
:
A_N B_N F_N

出力

问题的解决办法 在 1 行输出。 没有


入力例 1

5 3
1 4 12
3 6 7
2 3 6
4 8 8
8 9 10

出力例 1

7

5 个区间,则该组的得分为 7 ,并且可以获得最高分数。


入力例 2

5 2
1 4 12
3 6 7
2 3 6
4 8 8
8 9 10

出力例 2

14

故事: 卡加米兹
问题: ey429
测试仪: kyuridenamida, kagamiz, japlj