P14355 [集训队互测 2025] 封印

你是一名大魔法师，现在遇到了 $n$ 只怪物，第 $i$ 只怪物的出现时间为 $[l_i, r_i)$，有经验值 $w_i$。对于怪物 $i$，你可以选择一个实数 $k_i \in [l_i, r_i]$，并在 $[l_i, k_i)$ 时间内施展封印术控制这只怪物。特别地，如果 $k_i = l_i$，表示你没有对这种怪物施展封印术。由于人是有极限的，在同一时刻，你最多对 $K$ 个怪物施展法术，$K$ 为给定常数。 你有一个熟练度 $W$，由于已经很久没有使用过封印术了，在 $0$ 时刻 $W = 0$。对于怪物 $i$，如果 $k_i = r_i$，那么就成功封印了这只怪物，所以在 $r_i$ 时刻熟练度就会增加 $w_i$；如果 $k_i < r_i$，那么怪物就会在 $k_i$ 时刻攻击你，使得熟练度重置为 $0$。 在任意时刻，你可以选择施展终极秘术，将时间线上的所有的 $n$ 只怪物变成 $W$ 枚金币，并带着它们离开。如果同一时刻发生多个事件（熟练度增加、熟练度重置、终极秘术），它们之间的生效顺序可以任意安排。 现在，请求出最多能带着多少枚金币离开。

第一行两个正整数 $n, K$。 接下来 $n$ 行，每行三个正整数 $l_i, r_i, w_i$，表示一只怪物。

输出一行一个整数表示答案。

### 样例 3 见附加文件中的 `ex_seal3.in/ans`，该样例符合子任务 5,6 的限制。 ### 样例解释 对于样例 1，取 $k_1 = 3, k_2 = 2, k_3 = 6$，那么 2 时刻 $W$ 重置为 0，3 时刻 $W$ 增加 1，6 时刻 $W$ 增加 1，此时可以获得 2 枚金币。容易发现不可能获得 3 枚金币。 ### 限制与约定 对于所有数据，$n, l_i, r_i, w_i, K$ 均为正整数，$1 \leq K \leq n \leq 3 \times 10^5$, $1 \leq w_i \leq 10^9$, $1 \leq l_i < r_i \leq 2n$，且保证 $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$ 构成 $1 \sim 2n$ 的排列。 各子任务特殊约束及分值如下： | 子任务编号 | $n \leq$ | 特殊性质 | 分值 | 子任务依赖 | | :--: | :--: | :--: | :--: | :--: | | 1 | $20$ | - | $5$ | - | | 2 | $2500$ | $w_i = 1$ | $15$ | - | | 3 | $3 \times 10^5$ | $w_i = 1$ | $20$ | $2$ | | 4 | $2500$ | - | $15$ | $1, 2$ | | 5 | $10^5$ | $K \leq 30$ | $20$ | - | | 6 | $3 \times 10^5$ | - | $25$ | $3, 4, 5$ |