問題文
和真君要来参加休观场小学的运动会。 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