AT_k4pc_d.たのしい運動会(School Sports is Fun)

卡兹马今天来到了球感波小学的运动会。这次运动会有 $N$ 个比赛项目，每个项目的编号从 $0$ 到 $N-1$。

第 $i$ 个项目在时刻 $A_i$ 开始，时刻 $B_i$ 结束。如果卡兹马参与这个项目，他将获得 $F_i$ 的乐趣值。

由于操场足够大，可以同时进行多个项目，因此有些项目的时间可能会冲突。

卡兹马不能参与时间重叠的比赛。不过，如果一个项目刚结束，另一个项目立刻开始，他是可以参加的——即允许在结束和开始时间一致的情况下参与两个项目。

卡兹马希望能尽可能享受运动会的乐趣。但是在夏日炎炎的操场上，待得越久，他的精力就会消耗得越多，得到的乐趣值也会减少。具体而言，每参加 $1$ 单位时间，他的乐趣值会减少 $C$，即使不参与赛事也是如此。

因为卡兹马不太喜欢户外活动，所以他希望以最有效的方式参与运动会，尽量避开炎热。他可以在任意时间加入或退出运动会。

请你计算卡兹马所能获得的最大乐趣值。

格式为：$ N $ $ C $ $ A_1 $ $ B_1 $ $ F_1 $ ... $ A_N $ $ B_N $ $ F_N $

输出一个整数，表示所能获得的最大乐趣值。

给定 $N$ 个项目，其时间段由整数序列 $A$ 和 $B$ 定义。项目 $i$ 的时间是半开区间 $[A_i, B_i)$（包括 $A_i$，但不包括 $B_i$）。每个项目有一个权重 $F_i$。

需要考虑从这些不重叠的项目中选择一些，设选中的项目集为 $G$。

记 $L = \min \{A_i \mid i \in G\}$ 和 $R = \max \{B_i \mid i \in G\}$。集合 $G$ 的得分定义为 $(\sum_{i \in G} F_i) - C \times (R - L)$。当 $G$ 空时，得分为 $0$。

请通过选取合适的 $G$ 优化得分的最大值。

约束条件

• $1 \leq N \leq 10^5$
• $0 \leq C \leq 10^4$
• $0 \leq A_i < B_i \leq 10^5$
• $0 \leq F_i \leq 10^4$

另外，有部分条件限制的题目：

• 对于部分分，$N \leq 1000$。

本翻译由 AI 自动生成