题目描述

你是一名大魔法师，现在遇到了 $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 1
1 3 1
2 5 1
4 6 1

2

10 2
4 10 14
2 17 87
5 12 84
6 11 71
1 13 62
8 9 55
7 14 6
15 20 87
3 19 18
16 18 96

338

提示

样例 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$		$20$	$2$
4	$2500$	-	$15$	$1, 2$
5	$10^5$	$K \leq 30$	$20$	-
6	$3 \times 10^5$	-	$25$	$3, 4, 5$