你是一名大魔法师，现在遇到了 $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$ 的排列。

各子任务特殊约束及分值如下：