题目描述

众所周知，爆米花是一种真正的美食。为了今年的集训以及之后的聚会，你订购了 $N$ 种微波炉爆米花。每一种爆米花有三个参数：

• $A_i$：这种爆米花中任意一粒“爆开”的时间，单位为秒；
• $B_i$：这种爆米花中任意一粒“烧焦”的时间，单位为秒；
• $C_i$：这种爆米花的数量，单位为粒。

你还有 $M$ 个一次性爆米花袋，每个袋子的容量都非常大，可以认为是无限大，并且你有一台微波炉。

显然，没有人喜欢没爆开的爆米花，也没有人喜欢烧焦的爆米花。因此，你希望把这 $N$ 种爆米花合理地分配到 $M$ 个袋子中，然后依次把每个袋子放进微波炉，并为第 $j$ 个袋子设置一个烹饪时间 $prep_j$，使得经过 $M$ 批烹饪后，得到尽可能多的可食用爆米花。

形式化地说，如果第 $i$ 种爆米花被放入第 $j$ 个袋子中，并且第 $j$ 个袋子的烹饪时间为 $prep_j$，那么这种爆米花可食用，当且仅当：

给定 $N$ 种爆米花以及可用袋子的数量 $M$，你需要找到一种分配方案，以及每个袋子的最优烹饪时间，使最终可食用爆米花数量最大。输出这个最大数量。

输入格式

第一行包含两个自然数 $N,M$，含义如题所述。

接下来 $N$ 行，每行包含三个整数 $A_i,B_i,C_i$，表示第 $i$ 种爆米花的参数。

输出格式

包含一个自然数，表示最多能得到的可食用爆米花数量。

数据范围与约定

• $1 \le M \le N \le 200000$；
• $1 \le A_i < B_i \le 200000$；
• 爆米花总数量不超过 $10^9$；
• 有些袋子可以为空；
• 令

子任务如下：

样例 1

输入

5 2
2 4 3
1 5 6
4 8 10
7 8 2
10 11 2

输出

21

解释

共有 $5$ 种爆米花和 $2$ 个可用袋子。

一种可行的最优方案是：

• 袋子 $1$ 放入第 $1,2$ 种爆米花，烹饪时间设为 $3$；
• 袋子 $2$ 放入第 $3,4,5$ 种爆米花，烹饪时间设为 $7$。

除了第 $5$ 种爆米花仍然没有爆开以外，其余爆米花都能成功烹饪。因此答案为 $3+6+10+2=21$。

样例 2

输入

3 3
1 2 2
2 3 3
1 3 5

输出

10

解释

可以这样选择袋子：

• 袋子 $1$ 放入第 $1,3$ 种爆米花，烹饪时间设为 $1$；
• 袋子 $2$ 放入第 $2$ 种爆米花，烹饪时间设为 $2$；
• 袋子 $3$ 为空。