你是一名大魔法师，现在遇到了 $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\lt r_i$，那么怪物就会在 $k_i$ 时刻攻击你，使得熟练度重置为 $0$。
在任意时刻，你可以选择施展终极秘术，将时间线上的所有的 $n$ 只怪物变成 $W$ 枚金币，并带着它们离开。如果同一时刻发生多个事件（熟练度增加、熟练度重置、终极秘术），它们之间的生效顺序可以任意安排。
现在，请求出最多能带着多少枚金币离开。
输入格式
第一行两个正整数 $n,K$。
接下来 $n$ 行，每行三个正整数 $l_i,r_i,w_i$，表示一只怪物。
输出格式
输出一行一个整数表示答案。
样例
样例输入 1
3 1
1 3 1
2 5 1
4 6 1样例输出 1
2样例输入 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样例输出 2
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\leq10^9,1\leq l_i\lt r_i\leq 2n$，且保证 $l_1,l_2,\dots,l_n,r_1,r_2,\dots,r_n$ 构成 $1\sim 2n$ 的排列。
各子任务特殊约束及分值如下：
| 子任务编号 | $n\le$ | 特殊性质 | 分值 | 子任务依赖 |
|---|---|---|---|---|
| $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\le 30$ | $20$ | - |
| $6$ | $3\times 10^5$ | - | $25$ | $3,4,5$ |