该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

宝箱与卡牌

题目背景

小 G 来到了一条由 $n$ 个连续时刻组成的长廊。第 $i$ 个时刻有一个宝箱，如果小 G 当时没有被其他宝箱占用，就可以选择是否开始打开这个宝箱。

每个宝箱中都有两种奖励，但打开宝箱需要一定时间。小 G 想知道，在最后时刻结束前，自己最多能获得多少分数。

题目描述

一共有 $n$ 个连续时刻，编号为 $1,2,\ldots,n$。第 $i$ 个时刻有一个宝箱，打开它需要 $t_i$ 个时刻。

如果小 G 在时刻 $i$ 开始打开第 $i$ 个宝箱，那么：

• 他会占用从时刻 $i$ 到时刻 $i+t_i$ 的时间；
• 若 $i+t_i>n$，则这个宝箱无法在最后时刻前打开，不能选择；
• 打开完成后，他必须从以下两种卡牌中选择一种：
  • 道具卡：使之后获得的每一张分数卡都额外增加 $a_i$ 分；
  • 分数卡：立刻获得 $b_i$ 分，并额外获得此前所有道具卡带来的加成。

在任意没有被占用的时刻 $i$，小 G 也可以选择跳过第 $i$ 个宝箱，直接进入时刻 $i+1$。

小 G 最多只能获得 $K$ 张分数卡。道具卡数量没有限制。

请你求出，到第 $n$ 个时刻结束时，小 G 能获得的最大总分。

输入格式

第一行输入两个整数 $n,K$，表示时刻数量和最多能获得的分数卡数量。

接下来 $n$ 行，每行三个整数 $t_i,a_i,b_i$，表示第 $i$ 个宝箱的解锁时间、道具卡加成和分数卡基础分。

输出格式

输出一个整数，表示最大总分。

样例输入

5 2
0 3 4
1 10 1
0 0 8
0 2 6
0 0 5

样例输出

37

样例解释

一种最优方案如下：

• 在时刻 $1$ 打开宝箱，选择道具卡，此后每张分数卡额外增加 $3$ 分；
• 在时刻 $2$ 打开宝箱，解锁到时刻 $3$ 结束，选择道具卡，此后每张分数卡再额外增加 $10$ 分；
• 在时刻 $4$ 打开宝箱，选择分数卡，获得 $6+3+10=19$ 分；
• 在时刻 $5$ 打开宝箱，选择分数卡，获得 $5+3+10=18$ 分。

总分为 $19+18=37$。

数据范围

对于所有测试点，保证：

• $1\le n\le 2\times 10^5$
• $0\le K\le 500$
• $0\le t_i\le n$
• $0\le a_i,b_i\le 10^9$
• 答案不超过 $9\times 10^{18}$

子任务